<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 6.1.0">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.0.0/css/all.min.css">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.5.7/jquery.fancybox.min.css">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/pace/1.2.4/themes/green/pace-theme-minimal.css">
  <script src="https://cdnjs.cloudflare.com/ajax/libs/pace/1.2.4/pace.min.js" integrity="sha256-gqd7YTjg/BtfqWSwsJOvndl0Bxc8gFImLEkXQT8+qj0=" crossorigin="anonymous"></script>

<script class="next-config" data-name="main" type="application/json">{"hostname":"liukairui.me","root":"/","images":"/images","scheme":"Muse","darkmode":false,"version":"8.10.1","exturl":false,"sidebar":{"position":"left","display":"hide","padding":18,"offset":12},"copycode":true,"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":true,"pangu":true,"comments":{"style":"tabs","active":"valine","storage":true,"lazyload":false,"nav":null,"activeClass":"valine"},"stickytabs":false,"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}}</script><script src="/js/config.js"></script>

    <meta name="description" content="原题来自2020牛客寒假算法基础集训营3，作以存档备查">
<meta property="og:type" content="article">
<meta property="og:title" content="2020牛客寒假算法基础集训营3题解">
<meta property="og:url" content="http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A53%E9%A2%98%E8%A7%A3/">
<meta property="og:site_name" content="LiuKairui Website">
<meta property="og:description" content="原题来自2020牛客寒假算法基础集训营3，作以存档备查">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2020-10-30T16:00:09.000Z">
<meta property="article:modified_time" content="2021-10-18T06:44:13.581Z">
<meta property="article:author" content="Liu Kairui">
<meta property="article:tag" content="算法">
<meta property="article:tag" content="牛客">
<meta property="article:tag" content="ACM">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A53%E9%A2%98%E8%A7%A3/">



<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A53%E9%A2%98%E8%A7%A3/","path":"article/2020牛客寒假算法基础集训营3题解/","title":"2020牛客寒假算法基础集训营3题解"}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>2020牛客寒假算法基础集训营3题解 | LiuKairui Website</title>
  

  <script src="/js/third-party/analytics/baidu-analytics.js"></script>
  <script async src="https://hm.baidu.com/hm.js?ea07bceb8f5fa721da2ebf01833faa32"></script>



<div class="nindexBK">
<div class="nindexBKC"></div>
<div class="nindex">
  <h1>Hey👋</h1>
  <p style="font-weight: 500; font-size: 2.2em">欢迎访问Liu Kairui的个人站.</p>
  <p>
      我是一个来自重庆的在校大学生, 偏爱于前端技术<!--与OS设计-->, 偶尔使用 JS / Go 进行轻量项目开发, 欢迎访问我的
      <a href="https://github.com/KairuiLiu" target="_blank"><i class="fab fa-github-alt"></i> GitHub</a> .
  </p>
  <p>
      这个网站主要用来存储学习 / 瞎搞的笔记, 同时提供了邮件、图床等服务. 对于一些自认为有趣的<a href="javascript:;" id="myProj">项目</a>, 我也会将项目介绍, 文档, 甚至是设计指南发布在这里.
  </p>
  <ul>
    <li><p><a href="/artrank/" target="_blank">ArtRank</a>: 基于Node.JS的PageRank文献管理推荐系统</p></li>
    <li><p><a href="/gooj/" target="_blank">GoOJ</a>: 基于Golang的高校在线评测系统</p></li>
    <li><p><a href="/projects/" target="_blank">更多 <i class="fas fa-angle-right"></i></a></p></li>

  </ul>
  <p>
      可以在这些平台找到我: 
      <a href="https://www.zhihu.com/people/liu-kai-rui-18" target="_blank">知乎</a>,
      <a href="https://space.bilibili.com/33238144" target="_blank">bilibili</a>
      和
      <a href="https://www.coolapk.com/u/805314?from=qr" target="_blank">酷安</a>.
  </p>

  <p>
      下滑即可进入博客 <i class="fas fa-arrow-down"></i>
  </p>
</div>
</div>  

 
<script>
  var OriginTitile = document.title;
  var titleTime;
  document.addEventListener("visibilitychange", function() {
    if (document.hidden) {
      document.title = "谢谢离开 | " + OriginTitile;
      clearTimeout(titleTime);
    } else {
      document.title = "欢迎归来 | " + OriginTitile;
      titleTime = setTimeout(function() {
        document.title = OriginTitile;
      }, 2000);
    }
  });
</script>


<script>
  function checkIndex(){
    let nindexItems = [[".nindexBK","display","block","none"],[".headband","display","none","block"],["div.toggle.sidebar-toggle","visibility","hidden","visible"]]; // ,["button.darkmode-toggle","visibility","hidden","visible"]];
    let isIndex = new RegExp("^(\/){0,1}(index){0,1}(\.html){0,1}(/)*$").test(location.pathname);
    let backCanvas = document.querySelector(".nindexBK");
    nindexItems.dispShift = function (stat){this.forEach((e) => {try{document.querySelector(e[0]).style[e[1]]=e[2+stat];}catch{}})}
    if(isIndex){
      nindexItems.dispShift(0);
      window.onscroll=function(){
        if(document.documentElement.scrollTop>backCanvas.offsetHeight*1.05){
          nindexItems.dispShift(1);window.onscroll=null;
        }
      }
      document.querySelector("#myProj").onclick=()=>{
        let projlist = document.querySelector(".nindex>ul");
        projlist.className.indexOf("ulactive")==-1?projlist.classList.add("ulactive"):projlist.classList.remove("ulactive")
      }
    }else nindexItems.dispShift(1);
  }
  checkIndex();
</script>

<!--<script src="https://sdk.jinrishici.com/v2/browser/jinrishici.js" charset="utf-8"></script>-->

  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
<link rel="alternate" href="/atom.xml" title="LiuKairui Website" type="application/atom+xml">
<style>.darkmode--activated{--body-bg-color:#282828;--content-bg-color:#333;--card-bg-color:#555;--text-color:#ccc;--blockquote-color:#bbb;--link-color:#ccc;--link-hover-color:#eee;--brand-color:#ddd;--brand-hover-color:#ddd;--table-row-odd-bg-color:#282828;--table-row-hover-bg-color:#363636;--menu-item-bg-color:#555;--btn-default-bg:#222;--btn-default-color:#ccc;--btn-default-border-color:#555;--btn-default-hover-bg:#666;--btn-default-hover-color:#ccc;--btn-default-hover-border-color:#666;--highlight-background:#282b2e;--highlight-foreground:#a9b7c6;--highlight-gutter-background:#34393d;--highlight-gutter-foreground:#9ca9b6}.darkmode--activated img{opacity:.75}.darkmode--activated img:hover{opacity:.9}.darkmode--activated code{color:#69dbdc;background:0 0}button.darkmode-toggle{z-index:9999}.darkmode-ignore,img{display:flex!important}</style></head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <p class="site-title">LiuKairui Website</p>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">要有信仰</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu">
        <li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li>
        <li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li>
        <li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="fas fa-hashtag fa-fw"></i>标签</a></li>
        <li class="menu-item menu-item-收藏夹"><a href="/favorites/" rel="section"><i class="fab fa-gratipay fa-fw"></i>收藏夹</a></li>
        <li class="menu-item menu-item-留言板"><a href="/messageBoard/" rel="section"><i class="fab fa-facebook-messenger fa-fw"></i>留言板</a></li>
        <li class="menu-item menu-item-项目"><a href="/projects/" rel="section"><i class="fa fa-satellite fa-fw"></i>项目</a></li>
        <li class="menu-item menu-item-图床"><a href="http://img.liukairui.me/" rel="noopener" target="_blank"><i class="fa fa-bed fa-fw"></i>图床</a></li>
        <li class="menu-item menu-item-云ide"><a href="http://vsc.liukairui.me/" rel="noopener" target="_blank"><i class="fas fa-code fa-fw"></i>云IDE</a></li>
        <li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a></li>
        <li class="menu-item menu-item-邮箱"><a href="http://mail.liukairui.me/mail" rel="noopener" target="_blank"><i class="fas fa-envelope-open-text fa-fw"></i>邮箱</a></li>
        <li class="menu-item menu-item-rss"><a href="/atom.xml" rel="section"><i class="fa fa-rss fa-fw"></i>RSS</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup"><div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close" role="button">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#a%E7%89%9B%E7%89%9B%E7%9A%84drb%E8%BF%B7%E5%AE%ABi"><span class="nav-number">1.</span> <span class="nav-text">A：牛牛的DRB迷宫I</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#b%E7%89%9B%E7%89%9B%E7%9A%84drb%E8%BF%B7%E5%AE%ABii"><span class="nav-number">2.</span> <span class="nav-text">B：牛牛的DRB迷宫II</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#c%E7%89%9B%E7%89%9B%E7%9A%84%E6%95%B0%E7%BB%84%E8%B6%8A%E4%BD%8D"><span class="nav-number">3.</span> <span class="nav-text">C：牛牛的数组越位</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#d%E7%89%9B%E7%89%9B%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%95%B0%E7%BB%84%E5%AD%98%E5%82%A8"><span class="nav-number">4.</span> <span class="nav-text">D：牛牛与二叉树的数组存储</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#e%E7%89%9B%E7%89%9B%E7%9A%84%E9%9A%8F%E6%9C%BA%E6%95%B0"><span class="nav-number">5.</span> <span class="nav-text">E：牛牛的随机数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#f%E7%89%9B%E7%89%9B%E7%9A%84link-power-i"><span class="nav-number">6.</span> <span class="nav-text">F：牛牛的Link Power I</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#g%E7%89%9B%E7%89%9B%E7%9A%84link-power-ii"><span class="nav-number">7.</span> <span class="nav-text">G：牛牛的Link Power II</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#h%E7%89%9B%E7%89%9B%E7%9A%84k%E5%90%88%E5%9B%A0%E5%AD%90%E6%95%B0"><span class="nav-number">8.</span> <span class="nav-text">H：牛牛的k合因子数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#i%E7%89%9B%E7%89%9B%E7%9A%84%E6%B1%89%E8%AF%BA%E5%A1%94"><span class="nav-number">9.</span> <span class="nav-text">I：牛牛的汉诺塔</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#j-%E7%89%9B%E7%89%9B%E7%9A%84%E5%AE%9D%E5%8F%AF%E6%A2%A6go"><span class="nav-number">10.</span> <span class="nav-text">J： 牛牛的宝可梦Go</span></a></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="Liu Kairui"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">Liu Kairui</p>
  <div class="site-description" itemprop="description">LiuKairui Persional Website</div>
</div>
<div class="site-state-wrap site-overview-item animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">45</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
          <a href="/categories/">
        <span class="site-state-item-count">24</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
          <a href="/tags/">
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author site-overview-item animated">
      <span class="links-of-author-item">
        <a href="https://github.com/KairuiLiu" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;KairuiLiu" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:tclkr@live.com" title="E-Mail → mailto:tclkr@live.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://qm.qq.com/cgi-bin/qm/qr?k=oaf3ToOlN17hr5sHV98bT8qxsNYGaw5L&noverify=0" title="QQ → https:&#x2F;&#x2F;qm.qq.com&#x2F;cgi-bin&#x2F;qm&#x2F;qr?k&#x3D;oaf3ToOlN17hr5sHV98bT8qxsNYGaw5L&amp;noverify&#x3D;0" rel="noopener" target="_blank"><i class="fab fa-qq fa-fw"></i>QQ</a>
      </span>
      <span class="links-of-author-item">
        <a href="/atom.xml" title="RSS → &#x2F;atom.xml"><i class="fa fa-rss fa-fw"></i>RSS</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://liukairui.blog.csdn.net/" title="CSDN → https:&#x2F;&#x2F;liukairui.blog.csdn.net" rel="noopener" target="_blank"><i class="fab fa-cuttlefish fa-fw"></i>CSDN</a>
      </span>
      <span class="links-of-author-item">
        <a href="http://liukairui.cc/" title="国内站点 → http:&#x2F;&#x2F;liukairui.cc" rel="noopener" target="_blank"><i class="fa fa-globe fa-fw"></i>国内站点</a>
      </span>
  </div>
  <div class="cc-license site-overview-item animated" itemprop="license">
    <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" class="cc-opacity" rel="noopener" target="_blank"><img src="https://cdnjs.cloudflare.com/ajax/libs/creativecommons-vocabulary/2020.11.3/assets/license_badges/small/by_nc_sa.svg" alt="Creative Commons"></a>
  </div>


  <div class="links-of-blogroll site-overview-item animated">
    <div class="links-of-blogroll-title"><i class="fa fa-link fa-fw"></i>
      友情链接
    </div>
    <ul class="links-of-blogroll-list">
        <li class="links-of-blogroll-item">
          <a href="https://paste.ubuntu.com/" title="https:&#x2F;&#x2F;paste.ubuntu.com&#x2F;" rel="noopener" target="_blank">Ubuntu Pastebin</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://send.firefox.com/" title="https:&#x2F;&#x2F;send.firefox.com&#x2F;" rel="noopener" target="_blank">Firefox Send</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://jkwzs.cn/" title="https:&#x2F;&#x2F;jkwzs.cn&#x2F;" rel="noopener" target="_blank">南花醉笔丶の个人博客</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://ywrby.cn/" title="https:&#x2F;&#x2F;ywrby.cn&#x2F;" rel="noopener" target="_blank">Ywrby个人博客</a>
        </li>
    </ul>
  </div>

        </div>
      </div>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>
  <div class="reading-progress-bar"></div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A53%E9%A2%98%E8%A7%A3/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="Liu Kairui">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LiuKairui Website">
      <meta itemprop="description" content="LiuKairui Persional Website">
    </span>
    
    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="2020牛客寒假算法基础集训营3题解 | LiuKairui Website">
      <meta itemprop="description" content="原题来自2020牛客寒假算法基础集训营3，作以存档备查">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          2020牛客寒假算法基础集训营3题解
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2020-10-31 00:00:09" itemprop="dateCreated datePublished" datetime="2020-10-31T00:00:09+08:00">2020-10-31</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
        </span>
          ，
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E7%AE%97%E6%B3%95/%E9%A2%98%E8%A7%A3/" itemprop="url" rel="index"><span itemprop="name">题解</span></a>
        </span>
    </span>

  
    <span id="/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A53%E9%A2%98%E8%A7%A3/" class="post-meta-item leancloud_visitors" data-flag-title="2020牛客寒假算法基础集训营3题解" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
    <span class="post-meta-item-icon">
      <i class="far fa-comment"></i>
    </span>
    <span class="post-meta-item-text">Valine：</span>
  
    <a title="valine" href="/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A53%E9%A2%98%E8%A7%A3/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A53%E9%A2%98%E8%A7%A3/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

<script>
    CONFIG.hostname = location.hostname;
</script>
    <span class="post-meta-break"></span>
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>20k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>18 分钟</span>
    </span>
</div>

            <div class="post-description">原题来自2020牛客寒假算法基础集训营3，作以存档备查</div>
        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <h2 id="a牛牛的drb迷宫i">A：牛牛的DRB迷宫I</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200320144021809.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong> <pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">5</span> <span class="token number">5</span>
RBBBR
BBBBB
BBBDB
BDBBB
RBBBB</code></pre>
<strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">25</span></code></pre>
<hr />
<p>可以看到就是一个简单的dp题，然后再dp某一个点的时候，特判他能不能从左边和上边刷下来</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">const</span> <span class="token keyword">int</span> mod<span class="token operator">=</span><span class="token number">1000000007</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> dp<span class="token punctuation">[</span><span class="token number">75</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">75</span><span class="token punctuation">]</span><span class="token punctuation">,</span>n<span class="token punctuation">,</span>m<span class="token punctuation">;</span>
<span class="token keyword">char</span> G<span class="token punctuation">[</span><span class="token number">75</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">75</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">,</span><span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%s"</span><span class="token punctuation">,</span>G<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    dp<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>j<span class="token operator">&lt;=</span>m<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">></span><span class="token number">1</span><span class="token punctuation">)</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">+</span><span class="token punctuation">(</span>G<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">==</span><span class="token char">'R'</span><span class="token operator">?</span><span class="token number">0</span><span class="token operator">:</span>dp<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>j<span class="token operator">></span><span class="token number">1</span><span class="token punctuation">)</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">+</span><span class="token punctuation">(</span>G<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">==</span><span class="token char">'D'</span><span class="token operator">?</span><span class="token number">0</span><span class="token operator">:</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    cout<span class="token operator">&lt;&lt;</span>dp<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">[</span>m<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<hr />
<h2 id="b牛牛的drb迷宫ii">B：牛牛的DRB迷宫II</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200320144558560.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">25</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">5</span> <span class="token number">5</span>
RBBBR
BBBBB
BBBDB
BDBBB
RBBBB</code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">样例为《牛牛的DRB迷宫I》中的样例反过来。</code></pre>
<hr />
<p>首先，不要被这个样例给虎了，这就是第一题的样例反过来，不是出题人标程序跑出来的结果，
我们考虑构造一个50x50的地图最多可能的结果，就是所有的位置全是B，那么构造的结果是<span
class="math inline">\(C_{2n}^n \gg 10^9+7\)</span>，但是找不到规律qwq
于是构造一个二进制数，强制对角线为<span
class="math inline">\(2^n\)</span>，如图 <img
src="https://img-blog.csdnimg.cn/2020032015075871.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" />
首先，证明他的可行性，这样最大可以构造数字为<span
class="math inline">\(2^{50}&gt;2^{32}&gt;10^9+7\)</span>，说以这样构造是可行的
然后考虑如何构造这样的一个迷宫,由于数字只能从左上到右下流动，所以要想2倍，比较好的方法是
<img
src="https://img-blog.csdnimg.cn/20200320151406890.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> 那么，我们的构造方法是 <img
src="https://img-blog.csdnimg.cn/20200320151705500.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" />
左上角的绿块一定要是<code>B</code>，右面那个可以是<code>B</code>也可以是<code>D</code>因为即使右边是B，向右流过去也不会影响下面的，但是有可能会影响64那个块，所以我们让右边一定是<code>D</code>，同理下面那个可以是<code>R</code>也可以是<code>B</code>，但是我们暂定为<code>R</code>,于是暂时构造迷宫如图
<img
src="https://img-blog.csdnimg.cn/20200320152131130.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <img
src="https://img-blog.csdnimg.cn/20200320152221972.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> 错的思路：
这就好办了，我们把给的数分解为二进制，0就不选，1就选，例如25=11001(2进制)
蓝色是选，绿色是不选 <img
src="https://img-blog.csdnimg.cn/20200320152614490.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> 于是写出代码</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">long</span> <span class="token keyword">long</span> k<span class="token punctuation">,</span>len<span class="token punctuation">;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%lld"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>k<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span>len<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token operator">&lt;&lt;</span>len<span class="token punctuation">)</span><span class="token operator">&lt;=</span>k<span class="token punctuation">;</span>len<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d %d\n"</span><span class="token punctuation">,</span>len<span class="token punctuation">,</span>len<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>len<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span>len<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>j<span class="token operator">-</span>i<span class="token operator">==</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">-</span>j<span class="token operator">==</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>k<span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">else</span> <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"D"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                k<span class="token operator">>>=</span><span class="token number">1</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">==</span>j<span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">&lt;</span>j<span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"D"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<p><strong>这是错的，因为我们的二进制不选，下一个就会受影响，如图</strong>
<img
src="https://img-blog.csdnimg.cn/20200320152828710.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> 所以这个对角线上的数字必须保留！
那如何优雅的表示选或者不选呢？？ 首先，右上方的数字这么填写呢？？
一旦填写往下走到对角线上就会对对角线造成干扰，如图 <img
src="https://img-blog.csdnimg.cn/20200320153151452.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" />
所以，不要让他对对角线造成干扰，我们把右上方黄线全部设为<code>D</code>!!!
这样右上方白块全都是0了，右上全写<code>R</code> <img
src="https://img-blog.csdnimg.cn/20200320153437410.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <img
src="https://img-blog.csdnimg.cn/20200320153608234.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> 我们想让右下角数字承担选择转运的作用
首先一个要选的数字不能向右走，我们构造如下，首先把最后一个128要删去了，为啥，最后一个要放ans，我们假设<code>77</code>是最后要的结果
<img
src="https://img-blog.csdnimg.cn/20200320154313549.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> 让蓝色承担往下走的功能，红色是往右走 <img
src="https://img-blog.csdnimg.cn/20200320154629276.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> 那如何让数据往下流呢？ <img
src="https://img-blog.csdnimg.cn/20200320154715901.png"
alt="在这里插入图片描述" /> 比如现在他就流不下来 这么处理呢？
把他改成红色 <img
src="https://img-blog.csdnimg.cn/20200320154834148.png"
alt="在这里插入图片描述" /> 这就流下卡了
那么我们就让想让他流下来的写成B，不想流下来的写成R，就这样就做到了 <img
src="https://img-blog.csdnimg.cn/20200320155101643.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" />
所以，我们就做到了这一点，例如我们要处理一个<code>77</code>这样写 77=
1001101(二进制) <img
src="https://img-blog.csdnimg.cn/20200320155609658.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <img
src="https://img-blog.csdnimg.cn/20200320155801471.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>错误思路！！！：</strong>
轻松写出代码</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">long</span> <span class="token keyword">long</span> k<span class="token punctuation">,</span>len<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%lld"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>k<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span>len<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token operator">&lt;&lt;</span>len<span class="token punctuation">)</span><span class="token operator">&lt;=</span>k<span class="token punctuation">;</span>len<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token operator">&lt;&lt;</span>len<span class="token punctuation">)</span><span class="token operator">==</span>k<span class="token punctuation">)</span>len<span class="token operator">++</span><span class="token punctuation">;</span>len<span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%lld %lld\n"</span><span class="token punctuation">,</span>len<span class="token punctuation">,</span>len<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>len<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span>len<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">==</span>j<span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>j<span class="token operator">-</span>i<span class="token operator">==</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"D"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>j<span class="token operator">-</span>i<span class="token operator">></span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">-</span>j<span class="token operator">></span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token punctuation">(</span>i<span class="token operator">==</span>len<span class="token operator">-</span><span class="token number">1</span><span class="token operator">?</span><span class="token string">"R"</span><span class="token operator">:</span><span class="token string">"D"</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>k<span class="token operator">&amp;</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">else</span> <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                k<span class="token operator">>>=</span><span class="token number">1</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<p>有问题！！ <img
src="https://img-blog.csdnimg.cn/20200320155948404.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" />
这个灰色的表格，他是构造的时候让他构造主对角线才写为<code>D</code>,但是我们不能让他往下走，现在最后一个表格不是<span
class="math inline">\(2^n\)</span>了，写为<code>R</code> <img
src="https://img-blog.csdnimg.cn/2020032016023510.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> 所以再加一个特判</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">long</span> <span class="token keyword">long</span> k<span class="token punctuation">,</span>len<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%lld"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>k<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span>len<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token operator">&lt;&lt;</span>len<span class="token punctuation">)</span><span class="token operator">&lt;=</span>k<span class="token punctuation">;</span>len<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token operator">&lt;&lt;</span>len<span class="token punctuation">)</span><span class="token operator">==</span>k<span class="token punctuation">)</span>len<span class="token operator">++</span><span class="token punctuation">;</span>len<span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%lld %lld\n"</span><span class="token punctuation">,</span>len<span class="token punctuation">,</span>len<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>len<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span>len<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">==</span>len<span class="token operator">-</span><span class="token number">2</span><span class="token operator">&amp;&amp;</span>j<span class="token operator">==</span>len<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">==</span>j<span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>j<span class="token operator">-</span>i<span class="token operator">==</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"D"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>j<span class="token operator">-</span>i<span class="token operator">></span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">-</span>j<span class="token operator">></span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token punctuation">(</span>i<span class="token operator">==</span>len<span class="token operator">-</span><span class="token number">1</span><span class="token operator">?</span><span class="token string">"R"</span><span class="token operator">:</span><span class="token string">"D"</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>k<span class="token operator">&amp;</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">else</span> <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                k<span class="token operator">>>=</span><span class="token number">1</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<p>但只有case通过95% 有两个bug， 1. <span
class="math inline">\(k&gt;10^9+7\)</span>要mod回来 2.
k=0的时候的解，我试了三个方法，这个spj只支持最后一个</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token keyword">if</span><span class="token punctuation">(</span>k<span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"0 0"</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>k<span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"No solution"</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>k<span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"2 2\nBR\nDB"</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span></code></pre>
<p>最后写出AC代码</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">long</span> <span class="token keyword">long</span> k<span class="token punctuation">,</span>len<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%lld"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>k<span class="token punctuation">)</span><span class="token punctuation">;</span>
    k<span class="token operator">=</span>k<span class="token operator">%</span><span class="token number">1000000007</span><span class="token punctuation">;</span>
    <span class="token comment">// if(k==0)&#123;printf("0 0");return 0;&#125;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>k<span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"2 2\nBR\nDB"</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
    <span class="token comment">// if(k==0)&#123;printf("No solution");return 0;&#125;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span>len<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token operator">&lt;&lt;</span>len<span class="token punctuation">)</span><span class="token operator">&lt;=</span>k<span class="token punctuation">;</span>len<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token operator">&lt;&lt;</span>len<span class="token punctuation">)</span><span class="token operator">==</span>k<span class="token punctuation">)</span>len<span class="token operator">++</span><span class="token punctuation">;</span>len<span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%lld %lld\n"</span><span class="token punctuation">,</span>len<span class="token punctuation">,</span>len<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>len<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span>len<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">==</span>len<span class="token operator">-</span><span class="token number">2</span><span class="token operator">&amp;&amp;</span>j<span class="token operator">==</span>len<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">==</span>j<span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>j<span class="token operator">-</span>i<span class="token operator">==</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"D"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>j<span class="token operator">-</span>i<span class="token operator">></span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">-</span>j<span class="token operator">></span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token punctuation">(</span>i<span class="token operator">==</span>len<span class="token operator">-</span><span class="token number">1</span><span class="token operator">?</span><span class="token string">"R"</span><span class="token operator">:</span><span class="token string">"D"</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>k<span class="token operator">&amp;</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">else</span> <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                k<span class="token operator">>>=</span><span class="token number">1</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<p>真的是奇怪的构造qwq</p>
<hr />
<h2 id="c牛牛的数组越位">C：牛牛的数组越位</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200320162345326.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">4</span>
<span class="token number">2</span> <span class="token number">4</span> <span class="token number">8</span>
<span class="token operator">-</span><span class="token number">1</span> <span class="token number">4</span> <span class="token number">1</span>
<span class="token number">1</span> <span class="token operator">-</span><span class="token number">3</span> <span class="token number">2</span>
<span class="token number">2</span> <span class="token operator">-</span><span class="token number">6</span> <span class="token number">3</span>
<span class="token number">0</span> <span class="token number">3</span> <span class="token number">4</span>
<span class="token operator">-</span><span class="token number">1</span> <span class="token number">8</span> <span class="token number">5</span>
<span class="token operator">-</span><span class="token number">2</span> <span class="token number">13</span> <span class="token number">6</span>
<span class="token operator">-</span><span class="token number">100</span> <span class="token number">406</span> <span class="token number">7</span>
<span class="token number">100</span> <span class="token operator">-</span><span class="token number">393</span> <span class="token number">8</span>
<span class="token number">5</span> <span class="token number">5</span> <span class="token number">1</span>
<span class="token operator">-</span><span class="token number">1</span> <span class="token number">8</span> <span class="token number">1234</span>
<span class="token number">10</span> <span class="token number">10</span> <span class="token number">1</span>
<span class="token number">5</span> <span class="token operator">-</span><span class="token number">51</span> <span class="token number">1</span>
<span class="token number">1</span> <span class="token number">1</span> <span class="token number">1</span>
<span class="token number">0</span> <span class="token number">0</span> <span class="token number">7</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">1</span> <span class="token number">2</span> <span class="token number">3</span> <span class="token number">4</span>
<span class="token number">5</span> <span class="token number">6</span> <span class="token number">7</span> <span class="token number">8</span>
Undefined Behaviour
<span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">1234</span> <span class="token number">0</span>
<span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span>
<span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span>
<span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span>
<span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span> <span class="token number">0</span>
Undefined Behaviour
Runtime error
<span class="token number">7</span>
Accepted</code></pre>
<p><strong>备注:</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">无论是否发生数组越位或者非法访问，输入数据都要完整读入。
题目中的代码不符合C<span class="token operator">/</span>C<span class="token operator">++</span>规范，在不同编译器中由于实现不同运行的结果也可能不同，请勿依赖特定编译器对于UB的实现。<span class="token operator">:</span><span class="token punctuation">)</span></code></pre>
<hr />
<p>签到题，二维数组用一维模拟即可，但是比较奇怪的是比赛写的一直是TLE
AC代码</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">long</span> <span class="token keyword">long</span> a<span class="token punctuation">[</span><span class="token number">1103550</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> t<span class="token punctuation">;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>t<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>t<span class="token operator">--</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token function">memset</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> state<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">long</span> <span class="token keyword">long</span> n<span class="token punctuation">,</span>m<span class="token punctuation">,</span>p<span class="token punctuation">,</span>x<span class="token punctuation">,</span>y<span class="token punctuation">,</span>v<span class="token punctuation">;</span>
        <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%lld%lld%lld"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">,</span><span class="token operator">&amp;</span>m<span class="token punctuation">,</span><span class="token operator">&amp;</span>p<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>p<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%lld%lld%lld"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>x<span class="token punctuation">,</span><span class="token operator">&amp;</span>y<span class="token punctuation">,</span><span class="token operator">&amp;</span>v<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>state<span class="token operator">==</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token keyword">continue</span><span class="token punctuation">;</span>
            <span class="token keyword">long</span> <span class="token keyword">long</span> pos<span class="token operator">=</span>m<span class="token operator">*</span>x<span class="token operator">+</span>y<span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>pos<span class="token operator">&lt;</span><span class="token number">0</span><span class="token operator">||</span>pos<span class="token operator">></span>m<span class="token operator">*</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                state<span class="token operator">=</span><span class="token number">2</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            <span class="token keyword">else</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>x<span class="token operator">&lt;</span><span class="token number">0</span><span class="token operator">||</span>y<span class="token operator">&lt;</span><span class="token number">0</span><span class="token operator">||</span>x<span class="token operator">>=</span>n<span class="token operator">||</span>y<span class="token operator">>=</span>m<span class="token punctuation">)</span>
                    state<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
                a<span class="token punctuation">[</span>pos<span class="token punctuation">]</span><span class="token operator">=</span>v<span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>state<span class="token operator">==</span><span class="token number">2</span><span class="token punctuation">)</span>cout<span class="token operator">&lt;&lt;</span><span class="token string">"Runtime error"</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
        <span class="token keyword">else</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span>m<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span>cout<span class="token operator">&lt;&lt;</span>a<span class="token punctuation">[</span>i<span class="token operator">*</span>m<span class="token operator">+</span>j<span class="token punctuation">]</span><span class="token operator">&lt;&lt;</span><span class="token punctuation">(</span>j<span class="token operator">==</span>m<span class="token operator">-</span><span class="token number">1</span><span class="token operator">?</span><span class="token string">""</span><span class="token operator">:</span><span class="token string">" "</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                cout<span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            cout<span class="token operator">&lt;&lt;</span><span class="token punctuation">(</span>state<span class="token operator">==</span><span class="token number">1</span><span class="token operator">?</span><span class="token string">"Undefined Behaviour"</span><span class="token operator">:</span><span class="token string">"Accepted"</span><span class="token punctuation">)</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<hr />
<h2 id="d牛牛与二叉树的数组存储">D：牛牛与二叉树的数组存储</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200320165114655.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <img
src="https://img-blog.csdnimg.cn/20200320165130525.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <img
src="https://img-blog.csdnimg.cn/20200320165153451.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">7</span>
<span class="token number">1</span> <span class="token number">2</span> <span class="token number">3</span> <span class="token number">4</span> <span class="token number">5</span> <span class="token number">6</span> <span class="token number">7</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">The size of the tree is <span class="token number">7</span>
Node <span class="token number">1</span> is the root node of the tree
The father of node <span class="token number">1</span> is <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> the left child is <span class="token number">2</span><span class="token punctuation">,</span> <span class="token operator">and</span> the right child is <span class="token number">3</span>
The father of node <span class="token number">2</span> is <span class="token number">1</span><span class="token punctuation">,</span> the left child is <span class="token number">4</span><span class="token punctuation">,</span> <span class="token operator">and</span> the right child is <span class="token number">5</span>
The father of node <span class="token number">3</span> is <span class="token number">1</span><span class="token punctuation">,</span> the left child is <span class="token number">6</span><span class="token punctuation">,</span> <span class="token operator">and</span> the right child is <span class="token number">7</span>
The father of node <span class="token number">4</span> is <span class="token number">2</span><span class="token punctuation">,</span> the left child is <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">and</span> the right child is <span class="token operator">-</span><span class="token number">1</span>
The father of node <span class="token number">5</span> is <span class="token number">2</span><span class="token punctuation">,</span> the left child is <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">and</span> the right child is <span class="token operator">-</span><span class="token number">1</span>
The father of node <span class="token number">6</span> is <span class="token number">3</span><span class="token punctuation">,</span> the left child is <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">and</span> the right child is <span class="token operator">-</span><span class="token number">1</span>
The father of node <span class="token number">7</span> is <span class="token number">3</span><span class="token punctuation">,</span> the left child is <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">and</span> the right child is <span class="token operator">-</span><span class="token number">1</span></code></pre>
<p><strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">7</span>
<span class="token number">3</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token number">2</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token number">1</span> <span class="token number">4</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">The size of the tree is <span class="token number">4</span>
Node <span class="token number">3</span> is the root node of the tree
The father of node <span class="token number">1</span> is <span class="token number">2</span><span class="token punctuation">,</span> the left child is <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">and</span> the right child is <span class="token operator">-</span><span class="token number">1</span>
The father of node <span class="token number">2</span> is <span class="token number">3</span><span class="token punctuation">,</span> the left child is <span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">and</span> the right child is <span class="token number">4</span>
The father of node <span class="token number">3</span> is <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> the left child is <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">and</span> the right child is <span class="token number">2</span>
The father of node <span class="token number">4</span> is <span class="token number">2</span><span class="token punctuation">,</span> the left child is <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">and</span> the right child is <span class="token operator">-</span><span class="token number">1</span></code></pre>
<hr />
<p>前几天刚学了重口味线段树，即线段树的堆式存储 AC代码</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;algorithm></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">int</span> ss<span class="token punctuation">[</span><span class="token number">900050</span><span class="token punctuation">]</span><span class="token punctuation">,</span>n<span class="token punctuation">,</span>cnt<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>pos<span class="token punctuation">[</span><span class="token number">900050</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> k<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">char</span> f<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">char</span> c<span class="token operator">=</span><span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>c<span class="token operator">></span><span class="token char">'9'</span><span class="token operator">||</span>c<span class="token operator">&lt;</span><span class="token char">'0'</span><span class="token punctuation">)</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>c<span class="token operator">==</span><span class="token char">'-'</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            f<span class="token operator">=</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
            c<span class="token operator">=</span><span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>c<span class="token operator">&lt;=</span><span class="token char">'9'</span><span class="token operator">&amp;&amp;</span>c<span class="token operator">>=</span><span class="token char">'0'</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        k<span class="token operator">=</span>k<span class="token operator">*</span><span class="token number">10</span><span class="token operator">+</span>c<span class="token operator">-</span><span class="token char">'0'</span><span class="token punctuation">;</span>
        c<span class="token operator">=</span><span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> k<span class="token operator">*</span>f<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    n<span class="token operator">=</span><span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> t<span class="token operator">=</span><span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        ss<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>t<span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>t<span class="token operator">></span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>cnt<span class="token operator">++</span><span class="token punctuation">;</span>pos<span class="token punctuation">[</span>t<span class="token punctuation">]</span><span class="token operator">=</span>i<span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">int</span> root<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span>root<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>root<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>root<span class="token operator">++</span><span class="token punctuation">)</span><span class="token keyword">if</span><span class="token punctuation">(</span>ss<span class="token punctuation">[</span>root<span class="token punctuation">]</span><span class="token operator">!=</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token keyword">break</span><span class="token punctuation">;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token string">"The size of the tree is "</span><span class="token operator">&lt;&lt;</span>cnt<span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token string">"Node "</span><span class="token operator">&lt;&lt;</span>ss<span class="token punctuation">[</span>root<span class="token punctuation">]</span><span class="token operator">&lt;&lt;</span><span class="token string">" is the root node of the tree"</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>

    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>cnt<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        root<span class="token operator">=</span>pos<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
        cout<span class="token operator">&lt;&lt;</span><span class="token string">"The father of node "</span><span class="token operator">&lt;&lt;</span>ss<span class="token punctuation">[</span>root<span class="token punctuation">]</span><span class="token operator">&lt;&lt;</span><span class="token string">" is "</span><span class="token operator">&lt;&lt;</span><span class="token punctuation">(</span>ss<span class="token punctuation">[</span>root<span class="token operator">>></span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">0</span><span class="token operator">?</span><span class="token operator">-</span><span class="token number">1</span><span class="token operator">:</span>ss<span class="token punctuation">[</span>root<span class="token operator">>></span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">&lt;&lt;</span><span class="token string">", the left child is "</span><span class="token operator">&lt;&lt;</span><span class="token punctuation">(</span>ss<span class="token punctuation">[</span>root<span class="token operator">&lt;&lt;</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">0</span><span class="token operator">?</span><span class="token operator">-</span><span class="token number">1</span><span class="token operator">:</span>ss<span class="token punctuation">[</span>root<span class="token operator">&lt;&lt;</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">&lt;&lt;</span><span class="token string">", and the right child is "</span><span class="token operator">&lt;&lt;</span><span class="token punctuation">(</span>ss<span class="token punctuation">[</span><span class="token punctuation">(</span>root<span class="token operator">&lt;&lt;</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">0</span><span class="token operator">?</span><span class="token operator">-</span><span class="token number">1</span><span class="token operator">:</span>ss<span class="token punctuation">[</span><span class="token punctuation">(</span>root<span class="token operator">&lt;&lt;</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<hr />
<h2 id="e牛牛的随机数">E：牛牛的随机数</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200407081233666.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">2</span>
<span class="token number">3</span> <span class="token number">5</span> <span class="token number">7</span> <span class="token number">8</span>
<span class="token number">1</span> <span class="token number">3</span> <span class="token number">3</span> <span class="token number">5</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">500000011</span>
<span class="token number">222222228</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">a可取<span class="token number">3</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">5</span>，b可取<span class="token number">7</span><span class="token punctuation">,</span><span class="token number">8</span>
<span class="token number">3</span>⊕<span class="token number">7</span><span class="token operator">=</span><span class="token number">4</span>，<span class="token number">4</span>⊕<span class="token number">7</span><span class="token operator">=</span><span class="token number">3</span>，<span class="token number">5</span>⊕<span class="token number">7</span><span class="token operator">=</span><span class="token number">2</span>
<span class="token number">3</span>⊕<span class="token number">8</span><span class="token operator">=</span><span class="token number">11</span>，<span class="token number">4</span>⊕<span class="token number">8</span><span class="token operator">=</span><span class="token number">12</span>，<span class="token number">5</span>⊕<span class="token number">8</span><span class="token operator">=</span><span class="token number">13</span>
共<span class="token number">6</span>种情况，答案为<span class="token punctuation">(</span><span class="token number">4</span><span class="token operator">+</span><span class="token number">3</span><span class="token operator">+</span><span class="token number">2</span><span class="token operator">+</span><span class="token number">11</span><span class="token operator">+</span><span class="token number">12</span><span class="token operator">+</span><span class="token number">13</span><span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">6</span><span class="token operator">=</span><span class="token number">45</span><span class="token operator">/</span><span class="token number">6</span><span class="token operator">=</span><span class="token number">15</span><span class="token operator">/</span><span class="token number">2</span><span class="token operator">=</span><span class="token number">15</span><span class="token operator">*</span><span class="token number">2</span><span class="token operator">^</span><span class="token punctuation">(</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token function">mod</span><span class="token punctuation">(</span><span class="token number">10</span> <span class="token operator">^</span><span class="token number">9</span><span class="token operator">+</span><span class="token number">7</span><span class="token punctuation">)</span><span class="token operator">=</span><span class="token number">15</span><span class="token operator">*</span><span class="token number">500000004</span><span class="token operator">%</span>mod<span class="token operator">=</span><span class="token number">500000011</span></code></pre>
<hr />
<p>因为是区间计数问题，所以使用数位dp<br />
作者：四糸智乃<br />
链接：https://ac.nowcoder.com/discuss/365306?type=101&amp;order=0&amp;pos=1&amp;page=2<br />
来源：牛客网</p>
<p>有两种思路，第一种是拆位后直接数位DP。<br />
首先考虑二进制的个位产生的贡献，那么二进制个位产生的贡献有两部分：<br />
<span
class="math inline">\([l_1,r_1]\)</span>区间内个位为0的数字乘以#[l_2,r_2]$区间内个位为1的数字。<br />
<span
class="math inline">\([l_1,r_1]\)</span>区间内个位为1的数字乘以<span
class="math inline">\([l_2,r_2]\)</span>区间内个位为0的数字。<br />
做一个二进制位的数位DP，用于统计该数位0与1的个数。<br />
假设<span class="math inline">\(x \in
[l_1,R_1]中二进制的个位产生0的数目为￥cntx_0cnt二进制的个位产生1的数目为\)</span>cntx_1$<br />
<span class="math inline">\(y \in
[l_2,R_2]\)</span>中二进制的个位产生0的数目为<span
class="math inline">\(cnty_0\)</span>二进制的个位产生1的数目为<span
class="math inline">\(cnty_1\)</span><br />
那么就产生了<span
class="math inline">\(cnty_0*cntx_1+cntx_0*cnty_1\)</span>的贡献。<br />
如果是二进制的十位呢，那么就是<span
class="math inline">\((cnty_0*cntx_1+cntx_0*cnty_1)*2\)</span>。<br />
那么二进制的第k位的贡献就为<span
class="math inline">\((cnty_0*cntx_1+cntx_0*cnty_1)*2^k\)</span></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;bits/stdc++.h></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">long</span> <span class="token keyword">long</span> mod<span class="token operator">=</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token number">1e9</span><span class="token operator">+</span><span class="token number">7</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> i<span class="token punctuation">,</span>i0<span class="token punctuation">,</span>T<span class="token punctuation">;</span>
<span class="token keyword">long</span> <span class="token keyword">long</span> cnta<span class="token punctuation">[</span><span class="token number">70</span><span class="token punctuation">]</span><span class="token punctuation">,</span>cntb<span class="token punctuation">[</span><span class="token number">70</span><span class="token punctuation">]</span><span class="token punctuation">,</span>dp<span class="token punctuation">[</span><span class="token number">70</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">70</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">,</span>a<span class="token punctuation">[</span><span class="token number">70</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">long</span> <span class="token keyword">long</span> <span class="token function">dfs</span><span class="token punctuation">(</span><span class="token keyword">int</span> len<span class="token punctuation">,</span><span class="token keyword">bool</span> maxi<span class="token punctuation">,</span><span class="token keyword">int</span> k<span class="token punctuation">,</span><span class="token keyword">bool</span> f<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>len<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span>f<span class="token punctuation">]</span><span class="token operator">!=</span><span class="token operator">-</span><span class="token number">1</span><span class="token operator">&amp;&amp;</span>maxi<span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token keyword">return</span> dp<span class="token punctuation">[</span>len<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span>f<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">long</span> <span class="token keyword">long</span> cnt<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>len<span class="token punctuation">)</span><span class="token keyword">return</span> f<span class="token punctuation">;</span>
    <span class="token keyword">int</span> maxn<span class="token operator">=</span>maxi<span class="token operator">?</span>a<span class="token punctuation">[</span>len<span class="token punctuation">]</span><span class="token operator">:</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>maxn<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>cnt<span class="token operator">+=</span><span class="token function">dfs</span><span class="token punctuation">(</span>len<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span>maxi<span class="token operator">&amp;&amp;</span>i<span class="token operator">==</span>a<span class="token punctuation">[</span>len<span class="token punctuation">]</span><span class="token punctuation">,</span>k<span class="token punctuation">,</span>f<span class="token operator">||</span>len<span class="token operator">==</span>k<span class="token operator">&amp;&amp;</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> maxi<span class="token operator">?</span>cnt<span class="token operator">:</span>dp<span class="token punctuation">[</span>len<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span>f<span class="token punctuation">]</span><span class="token operator">=</span>cnt<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">long</span> <span class="token keyword">long</span> <span class="token function">div</span><span class="token punctuation">(</span><span class="token keyword">long</span> <span class="token keyword">long</span> tmp<span class="token punctuation">,</span><span class="token keyword">int</span> k<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token function">memset</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> p<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>tmp<span class="token punctuation">)</span>a<span class="token punctuation">[</span><span class="token operator">++</span>p<span class="token punctuation">]</span><span class="token operator">=</span>tmp<span class="token operator">%</span><span class="token number">2</span><span class="token punctuation">,</span>tmp<span class="token operator">/=</span><span class="token number">2</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token function">dfs</span><span class="token punctuation">(</span>p<span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>k<span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">long</span> <span class="token keyword">long</span> <span class="token function">inv</span><span class="token punctuation">(</span><span class="token keyword">long</span> <span class="token keyword">long</span> x<span class="token punctuation">,</span><span class="token keyword">long</span> <span class="token keyword">long</span> mod<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token keyword">long</span> <span class="token keyword">long</span> k<span class="token operator">=</span>mod<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">,</span>ans<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>k<span class="token punctuation">)</span>
    <span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>k<span class="token operator">&amp;</span><span class="token number">1</span><span class="token punctuation">)</span> ans<span class="token operator">=</span>ans<span class="token operator">*</span>x<span class="token operator">%</span>mod<span class="token punctuation">;</span>
        x<span class="token operator">=</span>x<span class="token operator">*</span>x<span class="token operator">%</span>mod<span class="token punctuation">;</span>
        k<span class="token operator">>>=</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> ans<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token function">memset</span><span class="token punctuation">(</span>dp<span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>dp<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>T<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>T<span class="token operator">--</span><span class="token punctuation">)</span>
    <span class="token punctuation">&#123;</span>
        <span class="token keyword">long</span> <span class="token keyword">long</span> l1<span class="token punctuation">,</span>r1<span class="token punctuation">,</span>l2<span class="token punctuation">,</span>r2<span class="token punctuation">,</span>p<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">,</span>ans<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%lld %lld %lld %lld"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>l1<span class="token punctuation">,</span><span class="token operator">&amp;</span>r1<span class="token punctuation">,</span><span class="token operator">&amp;</span>l2<span class="token punctuation">,</span><span class="token operator">&amp;</span>r2<span class="token punctuation">)</span><span class="token punctuation">;</span>
        l1<span class="token operator">--</span><span class="token punctuation">,</span>l2<span class="token operator">--</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span><span class="token number">60</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">,</span>p<span class="token operator">*=</span><span class="token number">2</span><span class="token punctuation">)</span>
        <span class="token punctuation">&#123;</span>
            cnta<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">div</span><span class="token punctuation">(</span>r1<span class="token punctuation">,</span>i<span class="token punctuation">)</span><span class="token operator">-</span><span class="token function">div</span><span class="token punctuation">(</span>l1<span class="token punctuation">,</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
            cntb<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">div</span><span class="token punctuation">(</span>r2<span class="token punctuation">,</span>i<span class="token punctuation">)</span><span class="token operator">-</span><span class="token function">div</span><span class="token punctuation">(</span>l2<span class="token punctuation">,</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
            ans<span class="token operator">+=</span><span class="token punctuation">(</span>cnta<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">%</span>mod<span class="token operator">*</span><span class="token punctuation">(</span><span class="token punctuation">(</span>r2<span class="token operator">-</span>l2<span class="token operator">-</span>cntb<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token operator">+</span>cntb<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">%</span>mod<span class="token operator">*</span><span class="token punctuation">(</span><span class="token punctuation">(</span>r1<span class="token operator">-</span>l1<span class="token operator">-</span>cnta<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>p<span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
            ans<span class="token operator">%=</span>mod<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        ans<span class="token operator">%=</span>mod<span class="token punctuation">,</span>ans<span class="token operator">+=</span>mod<span class="token punctuation">,</span>ans<span class="token operator">%=</span>mod<span class="token punctuation">;</span>
        ans<span class="token operator">=</span>ans<span class="token operator">*</span><span class="token function">inv</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token punctuation">(</span>r1<span class="token operator">-</span>l1<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span><span class="token punctuation">(</span>r2<span class="token operator">-</span>l2<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">,</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%lld\n"</span><span class="token punctuation">,</span>ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<h2 id="f牛牛的link-power-i">F：牛牛的Link Power I</h2>
<p><img
src="https://img-blog.csdnimg.cn/2020032016563852.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">3</span>
<span class="token number">101</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">2</span></code></pre>
<p><strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">5</span>
<span class="token number">00110</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">1</span></code></pre>
<p><strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">6</span>
<span class="token number">000010</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">0</span></code></pre>
<hr />
<p>记录每个1点的位置 对于第i个点，我们只要计算他以前的点即可 定义<span
class="math inline">\(pos_i\)</span>是第i个节点的位置<span
class="math inline">\(sum \_ pos_i\)</span>是前i个位置的<span
class="math inline">\(pos\)</span>和，对于第i个位置 以前的节点和为 <span
class="math display">\[
     \sum \limits_{j=1}^{i}\left \{ pos_i-pos_j \right \}
    =  \sum \limits_{j=1}^{i}pos_i-sum \_ pos_{i-1}=i \times pos_i - sum
\_ pos_{i-1}
\]</span> 写一个前缀和得到<span class="math inline">\(sum \_
pos_i\)</span> 代码 <pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;algorithm></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">const</span> <span class="token keyword">int</span> mod<span class="token operator">=</span><span class="token number">1000000007</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> cnt<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>n<span class="token punctuation">,</span>pos<span class="token punctuation">[</span><span class="token number">100050</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">char</span> ss<span class="token punctuation">[</span><span class="token number">100050</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">long</span> <span class="token keyword">long</span> ans<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%s"</span><span class="token punctuation">,</span>ss<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>ss<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span><span class="token char">'1'</span><span class="token punctuation">)</span>pos<span class="token punctuation">[</span>cnt<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">int</span> k<span class="token operator">=</span><span class="token operator">-</span><span class="token punctuation">(</span>cnt<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>cnt<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">,</span>k<span class="token operator">+=</span><span class="token number">2</span><span class="token punctuation">)</span>ans<span class="token operator">=</span><span class="token punctuation">(</span>ans<span class="token operator">+</span><span class="token punctuation">(</span>k<span class="token operator">*</span>pos<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
    cout<span class="token operator">&lt;&lt;</span>ans<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre></p>
<hr />
<h2 id="g牛牛的link-power-ii">G：牛牛的Link Power II</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200320171058726.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">5</span>
<span class="token number">00001</span>
<span class="token number">7</span>
<span class="token number">1</span> <span class="token number">1</span>
<span class="token number">2</span> <span class="token number">5</span>
<span class="token number">2</span> <span class="token number">1</span>
<span class="token number">1</span> <span class="token number">2</span>
<span class="token number">1</span> <span class="token number">4</span>
<span class="token number">1</span> <span class="token number">3</span>
<span class="token number">1</span> <span class="token number">1</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">0</span>
<span class="token number">4</span>
<span class="token number">0</span>
<span class="token number">0</span>
<span class="token number">0</span>
<span class="token number">2</span>
<span class="token number">4</span>
<span class="token number">10</span></code></pre>
<hr />
<p>修改由于要频繁修改我们使用线段树来处理对于第i的点，我们需要一个获得</p>
<ul>
<li>i前面所有1的pos和</li>
<li>i前面所有1的数目</li>
<li>i后面所有1的pos和</li>
<li>i后面所有1的数目</li>
</ul>
<p>对于查询一个区间我们需要两个数据作为返回值pair&lt;1的pos总和，1的数目&gt;,
所以线段树写成pair&lt;long long, long long&gt;数组的形式
注意pair合并的写法</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">LC</span> <span class="token expression"><span class="token punctuation">(</span>p<span class="token operator">&lt;&lt;</span><span class="token number">1</span><span class="token punctuation">)</span></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">RC</span> <span class="token expression"><span class="token punctuation">(</span>LC<span class="token operator">|</span><span class="token number">1</span><span class="token punctuation">)</span></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">M</span> <span class="token expression"><span class="token punctuation">(</span><span class="token punctuation">(</span>l<span class="token operator">+</span>r<span class="token punctuation">)</span><span class="token operator">>></span><span class="token number">1</span><span class="token punctuation">)</span></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">mod</span> <span class="token expression"><span class="token number">1000000007</span></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">MAX_N</span> <span class="token expression"><span class="token number">100050</span></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">typedef</span> pair<span class="token operator">&lt;</span><span class="token keyword">long</span> <span class="token keyword">long</span><span class="token punctuation">,</span><span class="token keyword">long</span> <span class="token keyword">long</span><span class="token operator">></span> PII<span class="token punctuation">;</span>      <span class="token comment">//pos cnt</span>
<span class="token keyword">int</span> n<span class="token punctuation">,</span>m<span class="token punctuation">;</span>
<span class="token keyword">long</span> <span class="token keyword">long</span> sumn<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>cnt<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>ans<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
PII ss<span class="token punctuation">[</span>MAX_N<span class="token operator">&lt;&lt;</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">up</span><span class="token punctuation">(</span><span class="token keyword">int</span> p<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    ss<span class="token punctuation">[</span>p<span class="token punctuation">]</span><span class="token punctuation">.</span>first<span class="token operator">=</span><span class="token punctuation">(</span>ss<span class="token punctuation">[</span>LC<span class="token punctuation">]</span><span class="token punctuation">.</span>first<span class="token operator">+</span>ss<span class="token punctuation">[</span>RC<span class="token punctuation">]</span><span class="token punctuation">.</span>first<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
    ss<span class="token punctuation">[</span>p<span class="token punctuation">]</span><span class="token punctuation">.</span>second<span class="token operator">=</span><span class="token punctuation">(</span>ss<span class="token punctuation">[</span>LC<span class="token punctuation">]</span><span class="token punctuation">.</span>second<span class="token operator">+</span>ss<span class="token punctuation">[</span>RC<span class="token punctuation">]</span><span class="token punctuation">.</span>second<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">void</span> <span class="token function">modify</span><span class="token punctuation">(</span><span class="token keyword">int</span> p<span class="token punctuation">,</span><span class="token keyword">int</span> x<span class="token punctuation">,</span><span class="token keyword">int</span> v<span class="token punctuation">,</span><span class="token keyword">int</span> l<span class="token punctuation">,</span><span class="token keyword">int</span> r<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>l<span class="token operator">==</span>r<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>v<span class="token operator">==</span><span class="token number">1</span><span class="token punctuation">)</span>ss<span class="token punctuation">[</span>p<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">make_pair</span><span class="token punctuation">(</span>l<span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>v<span class="token operator">==</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>ss<span class="token punctuation">[</span>p<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">make_pair</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>x<span class="token operator">&lt;=</span>M<span class="token punctuation">)</span><span class="token function">modify</span><span class="token punctuation">(</span>LC<span class="token punctuation">,</span>x<span class="token punctuation">,</span>v<span class="token punctuation">,</span>l<span class="token punctuation">,</span>M<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>x<span class="token operator">></span>M<span class="token punctuation">)</span><span class="token function">modify</span><span class="token punctuation">(</span>RC<span class="token punctuation">,</span>x<span class="token punctuation">,</span>v<span class="token punctuation">,</span>M<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>r<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">up</span><span class="token punctuation">(</span>p<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
PII <span class="token function">quary</span><span class="token punctuation">(</span><span class="token keyword">int</span> p<span class="token punctuation">,</span><span class="token keyword">int</span> x<span class="token punctuation">,</span><span class="token keyword">int</span> y<span class="token punctuation">,</span><span class="token keyword">int</span> l<span class="token punctuation">,</span><span class="token keyword">int</span> r<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>x<span class="token operator">></span>y<span class="token punctuation">)</span><span class="token keyword">return</span> <span class="token function">make_pair</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>x<span class="token operator">&lt;=</span>l<span class="token operator">&amp;&amp;</span>r<span class="token operator">&lt;=</span>y<span class="token punctuation">)</span><span class="token keyword">return</span> ss<span class="token punctuation">[</span>p<span class="token punctuation">]</span><span class="token punctuation">;</span>
    PII res<span class="token operator">=</span><span class="token function">make_pair</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>x<span class="token operator">&lt;=</span>M<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        PII tmp<span class="token operator">=</span><span class="token function">quary</span><span class="token punctuation">(</span>LC<span class="token punctuation">,</span>x<span class="token punctuation">,</span>y<span class="token punctuation">,</span>l<span class="token punctuation">,</span>M<span class="token punctuation">)</span><span class="token punctuation">;</span>
        res<span class="token punctuation">.</span>first<span class="token operator">=</span><span class="token punctuation">(</span>res<span class="token punctuation">.</span>first<span class="token operator">+</span>tmp<span class="token punctuation">.</span>first<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
        res<span class="token punctuation">.</span>second<span class="token operator">=</span><span class="token punctuation">(</span>res<span class="token punctuation">.</span>second<span class="token operator">+</span>tmp<span class="token punctuation">.</span>second<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>y<span class="token operator">></span>M<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        PII tmp<span class="token operator">=</span><span class="token function">quary</span><span class="token punctuation">(</span>RC<span class="token punctuation">,</span>x<span class="token punctuation">,</span>y<span class="token punctuation">,</span>M<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>r<span class="token punctuation">)</span><span class="token punctuation">;</span>
        res<span class="token punctuation">.</span>first<span class="token operator">=</span><span class="token punctuation">(</span>res<span class="token punctuation">.</span>first<span class="token operator">+</span>tmp<span class="token punctuation">.</span>first<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
        res<span class="token punctuation">.</span>second<span class="token operator">=</span><span class="token punctuation">(</span>res<span class="token punctuation">.</span>second<span class="token operator">+</span>tmp<span class="token punctuation">.</span>second<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> res<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">char</span> tmp<span class="token punctuation">;</span>
        <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%c"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>tmp<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>tmp<span class="token operator">==</span><span class="token char">'1'</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token function">modify</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span>i<span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
            ans<span class="token operator">=</span><span class="token punctuation">(</span>ans<span class="token operator">+</span>i<span class="token operator">*</span><span class="token punctuation">(</span>cnt<span class="token operator">++</span><span class="token punctuation">)</span><span class="token operator">-</span>sumn<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
            sumn<span class="token operator">+=</span>i<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%lld\n"</span><span class="token punctuation">,</span>ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>m<span class="token operator">--</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> op<span class="token punctuation">,</span>pos<span class="token punctuation">;</span>
        <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>op<span class="token punctuation">,</span><span class="token operator">&amp;</span>pos<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>op<span class="token operator">==</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token function">modify</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span>pos<span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
            PII l<span class="token operator">=</span><span class="token function">quary</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>pos<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>n<span class="token punctuation">)</span><span class="token punctuation">,</span>r<span class="token operator">=</span><span class="token function">quary</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span>pos<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>n<span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">long</span> <span class="token keyword">long</span> LA<span class="token operator">=</span><span class="token punctuation">(</span>l<span class="token punctuation">.</span>second<span class="token operator">*</span>pos<span class="token operator">-</span>l<span class="token punctuation">.</span>first<span class="token operator">+</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">,</span>RA<span class="token operator">=</span><span class="token punctuation">(</span>r<span class="token punctuation">.</span>first<span class="token operator">-</span>r<span class="token punctuation">.</span>second<span class="token operator">*</span>pos<span class="token operator">+</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
            ans<span class="token operator">=</span><span class="token punctuation">(</span>ans<span class="token operator">+</span>LA<span class="token operator">+</span>RA<span class="token operator">+</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
            <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%lld\n"</span><span class="token punctuation">,</span>ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token keyword">else</span><span class="token punctuation">&#123;</span>
            <span class="token function">modify</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span>pos<span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
            PII l<span class="token operator">=</span><span class="token function">quary</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>pos<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>n<span class="token punctuation">)</span><span class="token punctuation">,</span>r<span class="token operator">=</span><span class="token function">quary</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span>pos<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>n<span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">long</span> <span class="token keyword">long</span> LA<span class="token operator">=</span><span class="token punctuation">(</span>l<span class="token punctuation">.</span>second<span class="token operator">*</span>pos<span class="token operator">-</span>l<span class="token punctuation">.</span>first<span class="token operator">+</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">,</span>RA<span class="token operator">=</span><span class="token punctuation">(</span>r<span class="token punctuation">.</span>first<span class="token operator">-</span>r<span class="token punctuation">.</span>second<span class="token operator">*</span>pos<span class="token operator">+</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
            ans<span class="token operator">=</span><span class="token punctuation">(</span>ans<span class="token operator">-</span>LA<span class="token operator">-</span>RA<span class="token operator">+</span>mod<span class="token operator">*</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
            <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%lld\n"</span><span class="token punctuation">,</span>ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span></code></pre>
<hr />
<h2 id="h牛牛的k合因子数">H：牛牛的k合因子数</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200320171701491.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">10</span> <span class="token number">5</span>
<span class="token number">1</span>
<span class="token number">2</span>
<span class="token number">3</span>
<span class="token number">4</span>
<span class="token number">5</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">4</span>
<span class="token number">1</span>
<span class="token number">0</span>
<span class="token number">0</span>
<span class="token number">0</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">1</span><span class="token operator">~</span><span class="token number">10</span>的范围内
<span class="token number">1</span>合因子数有：<span class="token number">4</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token number">10</span>，共<span class="token number">4</span>个
<span class="token number">2</span>合因子数有：<span class="token number">8</span>，共<span class="token number">1</span>一个</code></pre>
<hr />
<p>使用埃筛即可出解</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;algorithm></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">bool</span> is_prime<span class="token punctuation">[</span><span class="token number">100050</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> n<span class="token punctuation">,</span>m<span class="token punctuation">,</span>num_hy<span class="token punctuation">[</span><span class="token number">100050</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">es</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">memset</span><span class="token punctuation">(</span>is_prime<span class="token punctuation">,</span><span class="token boolean">true</span><span class="token punctuation">,</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>is_prime<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    is_prime<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">=</span>is_prime<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token boolean">false</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">2</span><span class="token punctuation">;</span> i<span class="token operator">*</span>i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i <span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span><span class="token comment">//判断改成i*i&lt;N </span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>is_prime<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> i<span class="token operator">*</span>i<span class="token punctuation">;</span> j <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> j <span class="token operator">+=</span> i<span class="token punctuation">)</span><span class="token punctuation">&#123;</span><span class="token comment">//从i*i开始就可以了 </span>
                is_prime<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>  
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    is_prime<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">=</span>is_prime<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token boolean">true</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">void</span> <span class="token function">jduge</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">*</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span>i<span class="token punctuation">;</span>i<span class="token operator">*</span>j<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>is_prime<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>num_hy<span class="token punctuation">[</span>i<span class="token operator">*</span>j<span class="token punctuation">]</span><span class="token operator">++</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span><span class="token comment">//cout&lt;&lt;">>> "&lt;&lt;i*j&lt;&lt;" have a hyz "&lt;&lt;i&lt;&lt;endl;&#125;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>is_prime<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>num_hy<span class="token punctuation">[</span>i<span class="token operator">*</span>j<span class="token punctuation">]</span><span class="token operator">++</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span><span class="token comment">//cout&lt;&lt;">>> "&lt;&lt;i*j&lt;&lt;" have a hyz "&lt;&lt;j&lt;&lt;endl;&#125;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">==</span>j<span class="token operator">&amp;&amp;</span><span class="token operator">!</span>is_prime<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>num_hy<span class="token punctuation">[</span>i<span class="token operator">*</span>j<span class="token punctuation">]</span><span class="token operator">--</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span><span class="token comment">//cout&lt;&lt;">>> "&lt;&lt;i*j&lt;&lt;" -- "&lt;&lt;j&lt;&lt;endl;&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">,</span><span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">es</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">jduge</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">sort</span><span class="token punctuation">(</span>num_hy<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>num_hy<span class="token operator">+</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>m<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> k<span class="token punctuation">;</span>
        <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>k<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d\n"</span><span class="token punctuation">,</span><span class="token function">upper_bound</span><span class="token punctuation">(</span>num_hy<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>num_hy<span class="token operator">+</span><span class="token number">1</span><span class="token operator">+</span>n<span class="token punctuation">,</span>k<span class="token punctuation">)</span><span class="token operator">-</span><span class="token function">lower_bound</span><span class="token punctuation">(</span>num_hy<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>num_hy<span class="token operator">+</span><span class="token number">1</span><span class="token operator">+</span>n<span class="token punctuation">,</span>k<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token comment">// cout&lt;&lt;"-------------------------------------------------"&lt;&lt;endl;</span>
    <span class="token comment">// for(int i=1;i&lt;=n;i++)cout&lt;&lt;num_hy[i]&lt;&lt;" ";</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<hr />
<h2 id="i牛牛的汉诺塔">I：牛牛的汉诺塔</h2>
<p><img
src="https://img-blog.csdnimg.cn/2020032017194149.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <img
src="https://img-blog.csdnimg.cn/20200320172031280.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">3</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">A<span class="token operator">-></span>B<span class="token operator">:</span><span class="token number">1</span>
A<span class="token operator">-></span>C<span class="token operator">:</span><span class="token number">3</span>
B<span class="token operator">-></span>A<span class="token operator">:</span><span class="token number">1</span>
B<span class="token operator">-></span>C<span class="token operator">:</span><span class="token number">1</span>
C<span class="token operator">-></span>A<span class="token operator">:</span><span class="token number">0</span>
C<span class="token operator">-></span>B<span class="token operator">:</span><span class="token number">1</span>
SUM<span class="token operator">:</span><span class="token number">7</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">A<span class="token operator">-></span>C
A<span class="token operator">-></span>B
C<span class="token operator">-></span>B
A<span class="token operator">-></span>C
B<span class="token operator">-></span>A
B<span class="token operator">-></span>C
A<span class="token operator">-></span>C
统计：
A<span class="token operator">-></span>B出现<span class="token number">1</span>次
A<span class="token operator">-></span>C出现<span class="token number">3</span>次
B<span class="token operator">-></span>C出现<span class="token number">1</span>次
B<span class="token operator">-></span>A出现<span class="token number">1</span>次
C<span class="token operator">-></span>B出现<span class="token number">1</span>次
总计<span class="token number">7</span>次</code></pre>
<hr />
<p>首先要解决的是总数的问题<span class="math inline">\(2^{n-1}\)</span>
<a
target="_blank" rel="noopener" href="https://blog.csdn.net/restarted_/article/details/90377777">解法见此</a></p>
<p>写下n=2-5的所有过程，可以发现规律 <pre class="language-cpp" data-language="cpp"><code class="language-cpp">A<span class="token operator">-></span>B<span class="token operator">=</span>（上一次）A<span class="token operator">-></span>C<span class="token operator">-></span>B
B<span class="token operator">-></span>C<span class="token operator">=</span>（上一次）B<span class="token operator">-></span>A<span class="token operator">-></span>C
C<span class="token operator">-></span>A<span class="token operator">=</span>（上一次）C<span class="token operator">-></span>B<span class="token operator">-></span>A</code></pre> 递归求解即可
递推代码丢了，上一个别人的 只留着打表的代码 <pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;algorithm></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cmath></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token keyword">long</span> <span class="token keyword">long</span> ans<span class="token punctuation">[</span><span class="token number">70</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">10</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token punctuation">&#123;</span>
    <span class="token punctuation">&#123;</span><span class="token number">0</span> <span class="token punctuation">,</span> <span class="token number">1</span> <span class="token punctuation">,</span> <span class="token number">0</span> <span class="token punctuation">,</span> <span class="token number">0</span> <span class="token punctuation">,</span> <span class="token number">0</span> <span class="token punctuation">,</span> <span class="token number">0</span> <span class="token punctuation">,</span> <span class="token number">1</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">1</span> <span class="token punctuation">,</span> <span class="token number">1</span> <span class="token punctuation">,</span> <span class="token number">0</span> <span class="token punctuation">,</span> <span class="token number">1</span> <span class="token punctuation">,</span> <span class="token number">0</span> <span class="token punctuation">,</span> <span class="token number">0</span> <span class="token punctuation">,</span> <span class="token number">3</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>        
	<span class="token punctuation">&#123;</span><span class="token number">1</span> <span class="token punctuation">,</span> <span class="token number">3</span> <span class="token punctuation">,</span> <span class="token number">1</span> <span class="token punctuation">,</span> <span class="token number">1</span> <span class="token punctuation">,</span> <span class="token number">0</span> <span class="token punctuation">,</span> <span class="token number">1</span> <span class="token punctuation">,</span> <span class="token number">7</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>        
	<span class="token punctuation">&#123;</span><span class="token number">4</span> <span class="token punctuation">,</span> <span class="token number">3</span> <span class="token punctuation">,</span> <span class="token number">1</span> <span class="token punctuation">,</span> <span class="token number">4</span> <span class="token punctuation">,</span> <span class="token number">2</span> <span class="token punctuation">,</span> <span class="token number">1</span> <span class="token punctuation">,</span> <span class="token number">15</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>       
	<span class="token punctuation">&#123;</span><span class="token number">4</span> <span class="token punctuation">,</span> <span class="token number">9</span> <span class="token punctuation">,</span> <span class="token number">6</span> <span class="token punctuation">,</span> <span class="token number">4</span> <span class="token punctuation">,</span> <span class="token number">2</span> <span class="token punctuation">,</span> <span class="token number">6</span> <span class="token punctuation">,</span> <span class="token number">31</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>       
	<span class="token punctuation">&#123;</span><span class="token number">15</span> <span class="token punctuation">,</span> <span class="token number">9</span> <span class="token punctuation">,</span> <span class="token number">6</span> <span class="token punctuation">,</span> <span class="token number">15</span> <span class="token punctuation">,</span> <span class="token number">12</span> <span class="token punctuation">,</span> <span class="token number">6</span> <span class="token punctuation">,</span> <span class="token number">63</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>    
	<span class="token punctuation">&#123;</span><span class="token number">15</span> <span class="token punctuation">,</span> <span class="token number">31</span> <span class="token punctuation">,</span> <span class="token number">27</span> <span class="token punctuation">,</span> <span class="token number">15</span> <span class="token punctuation">,</span> <span class="token number">12</span> <span class="token punctuation">,</span> <span class="token number">27</span> <span class="token punctuation">,</span> <span class="token number">127</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">58</span> <span class="token punctuation">,</span> <span class="token number">31</span> <span class="token punctuation">,</span> <span class="token number">27</span> <span class="token punctuation">,</span> <span class="token number">58</span> <span class="token punctuation">,</span> <span class="token number">54</span> <span class="token punctuation">,</span> <span class="token number">27</span> <span class="token punctuation">,</span> <span class="token number">255</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">58</span> <span class="token punctuation">,</span> <span class="token number">117</span> <span class="token punctuation">,</span> <span class="token number">112</span> <span class="token punctuation">,</span> <span class="token number">58</span> <span class="token punctuation">,</span> <span class="token number">54</span> <span class="token punctuation">,</span> <span class="token number">112</span> <span class="token punctuation">,</span> <span class="token number">511</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">229</span> <span class="token punctuation">,</span> <span class="token number">117</span> <span class="token punctuation">,</span> <span class="token number">112</span> <span class="token punctuation">,</span> <span class="token number">229</span> <span class="token punctuation">,</span> <span class="token number">224</span> <span class="token punctuation">,</span> <span class="token number">112</span> <span class="token punctuation">,</span> <span class="token number">1023</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">229</span> <span class="token punctuation">,</span> <span class="token number">459</span> <span class="token punctuation">,</span> <span class="token number">453</span> <span class="token punctuation">,</span> <span class="token number">229</span> <span class="token punctuation">,</span> <span class="token number">224</span> <span class="token punctuation">,</span> <span class="token number">453</span> <span class="token punctuation">,</span> <span class="token number">2047</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">912</span> <span class="token punctuation">,</span> <span class="token number">459</span> <span class="token punctuation">,</span> <span class="token number">453</span> <span class="token punctuation">,</span> <span class="token number">912</span> <span class="token punctuation">,</span> <span class="token number">906</span> <span class="token punctuation">,</span> <span class="token number">453</span> <span class="token punctuation">,</span> <span class="token number">4095</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">912</span> <span class="token punctuation">,</span> <span class="token number">1825</span> <span class="token punctuation">,</span> <span class="token number">1818</span> <span class="token punctuation">,</span> <span class="token number">912</span> <span class="token punctuation">,</span> <span class="token number">906</span> <span class="token punctuation">,</span> <span class="token number">1818</span> <span class="token punctuation">,</span> <span class="token number">8191</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">3643</span> <span class="token punctuation">,</span> <span class="token number">1825</span> <span class="token punctuation">,</span> <span class="token number">1818</span> <span class="token punctuation">,</span> <span class="token number">3643</span> <span class="token punctuation">,</span> <span class="token number">3636</span> <span class="token punctuation">,</span> <span class="token number">1818</span> <span class="token punctuation">,</span> <span class="token number">16383</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">3643</span> <span class="token punctuation">,</span> <span class="token number">7287</span> <span class="token punctuation">,</span> <span class="token number">7279</span> <span class="token punctuation">,</span> <span class="token number">3643</span> <span class="token punctuation">,</span> <span class="token number">3636</span> <span class="token punctuation">,</span> <span class="token number">7279</span> <span class="token punctuation">,</span> <span class="token number">32767</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">14566</span> <span class="token punctuation">,</span> <span class="token number">7287</span> <span class="token punctuation">,</span> <span class="token number">7279</span> <span class="token punctuation">,</span> <span class="token number">14566</span> <span class="token punctuation">,</span> <span class="token number">14558</span> <span class="token punctuation">,</span> <span class="token number">7279</span> <span class="token punctuation">,</span> <span class="token number">65535</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">14566</span> <span class="token punctuation">,</span> <span class="token number">29133</span> <span class="token punctuation">,</span> <span class="token number">29124</span> <span class="token punctuation">,</span> <span class="token number">14566</span> <span class="token punctuation">,</span> <span class="token number">14558</span> <span class="token punctuation">,</span> <span class="token number">29124</span> <span class="token punctuation">,</span> <span class="token number">131071</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">58257</span> <span class="token punctuation">,</span> <span class="token number">29133</span> <span class="token punctuation">,</span> <span class="token number">29124</span> <span class="token punctuation">,</span> <span class="token number">58257</span> <span class="token punctuation">,</span> <span class="token number">58248</span> <span class="token punctuation">,</span> <span class="token number">29124</span> <span class="token punctuation">,</span> <span class="token number">262143</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">58257</span> <span class="token punctuation">,</span> <span class="token number">116515</span> <span class="token punctuation">,</span> <span class="token number">116505</span> <span class="token punctuation">,</span> <span class="token number">58257</span> <span class="token punctuation">,</span> <span class="token number">58248</span> <span class="token punctuation">,</span> <span class="token number">116505</span> <span class="token punctuation">,</span> <span class="token number">524287</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">233020</span> <span class="token punctuation">,</span> <span class="token number">116515</span> <span class="token punctuation">,</span> <span class="token number">116505</span> <span class="token punctuation">,</span> <span class="token number">233020</span> <span class="token punctuation">,</span> <span class="token number">233010</span> <span class="token punctuation">,</span> <span class="token number">116505</span> <span class="token punctuation">,</span> <span class="token number">1048575</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">233020</span> <span class="token punctuation">,</span> <span class="token number">466041</span> <span class="token punctuation">,</span> <span class="token number">466030</span> <span class="token punctuation">,</span> <span class="token number">233020</span> <span class="token punctuation">,</span> <span class="token number">233010</span> <span class="token punctuation">,</span> <span class="token number">466030</span> <span class="token punctuation">,</span> <span class="token number">2097151</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">932071</span> <span class="token punctuation">,</span> <span class="token number">466041</span> <span class="token punctuation">,</span> <span class="token number">466030</span> <span class="token punctuation">,</span> <span class="token number">932071</span> <span class="token punctuation">,</span> <span class="token number">932060</span> <span class="token punctuation">,</span> <span class="token number">466030</span> <span class="token punctuation">,</span> <span class="token number">4194303</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">932071</span> <span class="token punctuation">,</span> <span class="token number">1864143</span> <span class="token punctuation">,</span> <span class="token number">1864131</span> <span class="token punctuation">,</span> <span class="token number">932071</span> <span class="token punctuation">,</span> <span class="token number">932060</span> <span class="token punctuation">,</span> <span class="token number">1864131</span> <span class="token punctuation">,</span> <span class="token number">8388607</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">3728274</span> <span class="token punctuation">,</span> <span class="token number">1864143</span> <span class="token punctuation">,</span> <span class="token number">1864131</span> <span class="token punctuation">,</span> <span class="token number">3728274</span> <span class="token punctuation">,</span> <span class="token number">3728262</span> <span class="token punctuation">,</span> <span class="token number">1864131</span> <span class="token punctuation">,</span> <span class="token number">16777215</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">3728274</span> <span class="token punctuation">,</span> <span class="token number">7456549</span> <span class="token punctuation">,</span> <span class="token number">7456536</span> <span class="token punctuation">,</span> <span class="token number">3728274</span> <span class="token punctuation">,</span> <span class="token number">3728262</span> <span class="token punctuation">,</span> <span class="token number">7456536</span> <span class="token punctuation">,</span> <span class="token number">33554431</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">14913085</span> <span class="token punctuation">,</span> <span class="token number">7456549</span> <span class="token punctuation">,</span> <span class="token number">7456536</span> <span class="token punctuation">,</span> <span class="token number">14913085</span> <span class="token punctuation">,</span> <span class="token number">14913072</span> <span class="token punctuation">,</span> <span class="token number">7456536</span> <span class="token punctuation">,</span> <span class="token number">67108863</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">14913085</span> <span class="token punctuation">,</span> <span class="token number">29826171</span> <span class="token punctuation">,</span> <span class="token number">29826157</span> <span class="token punctuation">,</span> <span class="token number">14913085</span> <span class="token punctuation">,</span> <span class="token number">14913072</span> <span class="token punctuation">,</span> <span class="token number">29826157</span> <span class="token punctuation">,</span> <span class="token number">134217727</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">59652328</span> <span class="token punctuation">,</span> <span class="token number">29826171</span> <span class="token punctuation">,</span> <span class="token number">29826157</span> <span class="token punctuation">,</span> <span class="token number">59652328</span> <span class="token punctuation">,</span> <span class="token number">59652314</span> <span class="token punctuation">,</span> <span class="token number">29826157</span> <span class="token punctuation">,</span> <span class="token number">268435455</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">59652328</span> <span class="token punctuation">,</span> <span class="token number">119304657</span> <span class="token punctuation">,</span> <span class="token number">119304642</span> <span class="token punctuation">,</span> <span class="token number">59652328</span> <span class="token punctuation">,</span> <span class="token number">59652314</span> <span class="token punctuation">,</span> <span class="token number">119304642</span> <span class="token punctuation">,</span> <span class="token number">536870911</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">238609299</span> <span class="token punctuation">,</span> <span class="token number">119304657</span> <span class="token punctuation">,</span> <span class="token number">119304642</span> <span class="token punctuation">,</span> <span class="token number">238609299</span> <span class="token punctuation">,</span> <span class="token number">238609284</span> <span class="token punctuation">,</span> <span class="token number">119304642</span> <span class="token punctuation">,</span> <span class="token number">1073741823</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">238609299</span> <span class="token punctuation">,</span> <span class="token number">477218599</span> <span class="token punctuation">,</span> <span class="token number">477218583</span> <span class="token punctuation">,</span> <span class="token number">238609299</span> <span class="token punctuation">,</span> <span class="token number">238609284</span> <span class="token punctuation">,</span> <span class="token number">477218583</span> <span class="token punctuation">,</span> <span class="token number">2147483647</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">954437182</span> <span class="token punctuation">,</span> <span class="token number">477218599</span> <span class="token punctuation">,</span> <span class="token number">477218583</span> <span class="token punctuation">,</span> <span class="token number">954437182</span> <span class="token punctuation">,</span> <span class="token number">954437166</span> <span class="token punctuation">,</span> <span class="token number">477218583</span> <span class="token punctuation">,</span> <span class="token number">4294967295</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">954437182</span> <span class="token punctuation">,</span> <span class="token number">1908874365</span> <span class="token punctuation">,</span> <span class="token number">1908874348</span> <span class="token punctuation">,</span> <span class="token number">954437182</span> <span class="token punctuation">,</span> <span class="token number">954437166</span> <span class="token punctuation">,</span> <span class="token number">1908874348</span> <span class="token punctuation">,</span> <span class="token number">8589934591</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">3817748713</span> <span class="token punctuation">,</span> <span class="token number">1908874365</span> <span class="token punctuation">,</span> <span class="token number">1908874348</span> <span class="token punctuation">,</span> <span class="token number">3817748713</span> <span class="token punctuation">,</span> <span class="token number">3817748696</span> <span class="token punctuation">,</span> <span class="token number">1908874348</span> <span class="token punctuation">,</span> <span class="token number">17179869183</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">3817748713</span> <span class="token punctuation">,</span> <span class="token number">7635497427</span> <span class="token punctuation">,</span> <span class="token number">7635497409</span> <span class="token punctuation">,</span> <span class="token number">3817748713</span> <span class="token punctuation">,</span> <span class="token number">3817748696</span> <span class="token punctuation">,</span> <span class="token number">7635497409</span> <span class="token punctuation">,</span> <span class="token number">34359738367</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">15270994836</span> <span class="token punctuation">,</span> <span class="token number">7635497427</span> <span class="token punctuation">,</span> <span class="token number">7635497409</span> <span class="token punctuation">,</span> <span class="token number">15270994836</span> <span class="token punctuation">,</span> <span class="token number">15270994818</span> <span class="token punctuation">,</span> <span class="token number">7635497409</span> <span class="token punctuation">,</span> <span class="token number">68719476735</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">15270994836</span> <span class="token punctuation">,</span> <span class="token number">30541989673</span> <span class="token punctuation">,</span> <span class="token number">30541989654</span> <span class="token punctuation">,</span> <span class="token number">15270994836</span> <span class="token punctuation">,</span> <span class="token number">15270994818</span> <span class="token punctuation">,</span> <span class="token number">30541989654</span> <span class="token punctuation">,</span> <span class="token number">137438953471</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">61083979327</span> <span class="token punctuation">,</span> <span class="token number">30541989673</span> <span class="token punctuation">,</span> <span class="token number">30541989654</span> <span class="token punctuation">,</span> <span class="token number">61083979327</span> <span class="token punctuation">,</span> <span class="token number">61083979308</span> <span class="token punctuation">,</span> <span class="token number">30541989654</span> <span class="token punctuation">,</span> <span class="token number">274877906943</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">61083979327</span> <span class="token punctuation">,</span> <span class="token number">122167958655</span> <span class="token punctuation">,</span> <span class="token number">122167958635</span> <span class="token punctuation">,</span> <span class="token number">61083979327</span> <span class="token punctuation">,</span> <span class="token number">61083979308</span> <span class="token punctuation">,</span> <span class="token number">122167958635</span> <span class="token punctuation">,</span> <span class="token number">549755813887</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">244335917290</span> <span class="token punctuation">,</span> <span class="token number">122167958655</span> <span class="token punctuation">,</span> <span class="token number">122167958635</span> <span class="token punctuation">,</span> <span class="token number">244335917290</span> <span class="token punctuation">,</span> <span class="token number">244335917270</span> <span class="token punctuation">,</span> <span class="token number">122167958635</span> <span class="token punctuation">,</span> <span class="token number">1099511627775</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">244335917290</span> <span class="token punctuation">,</span> <span class="token number">488671834581</span> <span class="token punctuation">,</span> <span class="token number">488671834560</span> <span class="token punctuation">,</span> <span class="token number">244335917290</span> <span class="token punctuation">,</span> <span class="token number">244335917270</span> <span class="token punctuation">,</span> <span class="token number">488671834560</span> <span class="token punctuation">,</span> <span class="token number">2199023255551</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">977343669141</span> <span class="token punctuation">,</span> <span class="token number">488671834581</span> <span class="token punctuation">,</span> <span class="token number">488671834560</span> <span class="token punctuation">,</span> <span class="token number">977343669141</span> <span class="token punctuation">,</span> <span class="token number">977343669120</span> <span class="token punctuation">,</span> <span class="token number">488671834560</span> <span class="token punctuation">,</span> <span class="token number">4398046511103</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">977343669141</span> <span class="token punctuation">,</span> <span class="token number">1954687338283</span> <span class="token punctuation">,</span> <span class="token number">1954687338261</span> <span class="token punctuation">,</span> <span class="token number">977343669141</span> <span class="token punctuation">,</span> <span class="token number">977343669120</span> <span class="token punctuation">,</span> <span class="token number">1954687338261</span> <span class="token punctuation">,</span> <span class="token number">8796093022207</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">3909374676544</span> <span class="token punctuation">,</span> <span class="token number">1954687338283</span> <span class="token punctuation">,</span> <span class="token number">1954687338261</span> <span class="token punctuation">,</span> <span class="token number">3909374676544</span> <span class="token punctuation">,</span> <span class="token number">3909374676522</span> <span class="token punctuation">,</span> <span class="token number">1954687338261</span> <span class="token punctuation">,</span> <span class="token number">17592186044415</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">3909374676544</span> <span class="token punctuation">,</span> <span class="token number">7818749353089</span> <span class="token punctuation">,</span> <span class="token number">7818749353066</span> <span class="token punctuation">,</span> <span class="token number">3909374676544</span> <span class="token punctuation">,</span> <span class="token number">3909374676522</span> <span class="token punctuation">,</span> <span class="token number">7818749353066</span> <span class="token punctuation">,</span> <span class="token number">35184372088831</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">15637498706155</span> <span class="token punctuation">,</span> <span class="token number">7818749353089</span> <span class="token punctuation">,</span> <span class="token number">7818749353066</span> <span class="token punctuation">,</span> <span class="token number">15637498706155</span> <span class="token punctuation">,</span> <span class="token number">15637498706132</span> <span class="token punctuation">,</span> <span class="token number">7818749353066</span> <span class="token punctuation">,</span> <span class="token number">70368744177663</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">15637498706155</span> <span class="token punctuation">,</span> <span class="token number">31274997412311</span> <span class="token punctuation">,</span> <span class="token number">31274997412287</span> <span class="token punctuation">,</span> <span class="token number">15637498706155</span> <span class="token punctuation">,</span> <span class="token number">15637498706132</span> <span class="token punctuation">,</span> <span class="token number">31274997412287</span> <span class="token punctuation">,</span> <span class="token number">140737488355327</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">62549994824598</span> <span class="token punctuation">,</span> <span class="token number">31274997412311</span> <span class="token punctuation">,</span> <span class="token number">31274997412287</span> <span class="token punctuation">,</span> <span class="token number">62549994824598</span> <span class="token punctuation">,</span> <span class="token number">62549994824574</span> <span class="token punctuation">,</span> <span class="token number">31274997412287</span> <span class="token punctuation">,</span> <span class="token number">281474976710655</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">62549994824598</span> <span class="token punctuation">,</span> <span class="token number">125099989649197</span> <span class="token punctuation">,</span> <span class="token number">125099989649172</span> <span class="token punctuation">,</span> <span class="token number">62549994824598</span> <span class="token punctuation">,</span> <span class="token number">62549994824574</span> <span class="token punctuation">,</span> <span class="token number">125099989649172</span> <span class="token punctuation">,</span> <span class="token number">562949953421311</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">250199979298369</span> <span class="token punctuation">,</span> <span class="token number">125099989649197</span> <span class="token punctuation">,</span> <span class="token number">125099989649172</span> <span class="token punctuation">,</span> <span class="token number">250199979298369</span> <span class="token punctuation">,</span> <span class="token number">250199979298344</span> <span class="token punctuation">,</span> <span class="token number">125099989649172</span> <span class="token punctuation">,</span> <span class="token number">1125899906842623</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">250199979298369</span> <span class="token punctuation">,</span> <span class="token number">500399958596739</span> <span class="token punctuation">,</span> <span class="token number">500399958596713</span> <span class="token punctuation">,</span> <span class="token number">250199979298369</span> <span class="token punctuation">,</span> <span class="token number">250199979298344</span> <span class="token punctuation">,</span> <span class="token number">500399958596713</span> <span class="token punctuation">,</span> <span class="token number">2251799813685247</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">1000799917193452</span> <span class="token punctuation">,</span> <span class="token number">500399958596739</span> <span class="token punctuation">,</span> <span class="token number">500399958596713</span> <span class="token punctuation">,</span> <span class="token number">1000799917193452</span> <span class="token punctuation">,</span> <span class="token number">1000799917193426</span> <span class="token punctuation">,</span> <span class="token number">500399958596713</span> <span class="token punctuation">,</span> <span class="token number">4503599627370495</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">1000799917193452</span> <span class="token punctuation">,</span> <span class="token number">2001599834386905</span> <span class="token punctuation">,</span> <span class="token number">2001599834386878</span> <span class="token punctuation">,</span> <span class="token number">1000799917193452</span> <span class="token punctuation">,</span> <span class="token number">1000799917193426</span> <span class="token punctuation">,</span> <span class="token number">2001599834386878</span> <span class="token punctuation">,</span> <span class="token number">9007199254740991</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">4003199668773783</span> <span class="token punctuation">,</span> <span class="token number">2001599834386905</span> <span class="token punctuation">,</span> <span class="token number">2001599834386878</span> <span class="token punctuation">,</span> <span class="token number">4003199668773783</span> <span class="token punctuation">,</span> <span class="token number">4003199668773756</span> <span class="token punctuation">,</span> <span class="token number">2001599834386878</span> <span class="token punctuation">,</span> <span class="token number">18014398509481983</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>        
	<span class="token punctuation">&#123;</span><span class="token number">4003199668773783</span> <span class="token punctuation">,</span> <span class="token number">8006399337547567</span> <span class="token punctuation">,</span> <span class="token number">8006399337547539</span> <span class="token punctuation">,</span> <span class="token number">4003199668773783</span> <span class="token punctuation">,</span> <span class="token number">4003199668773756</span> <span class="token punctuation">,</span> <span class="token number">8006399337547539</span> <span class="token punctuation">,</span> <span class="token number">36028797018963967</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>        
	<span class="token punctuation">&#123;</span><span class="token number">16012798675095106</span> <span class="token punctuation">,</span> <span class="token number">8006399337547567</span> <span class="token punctuation">,</span> <span class="token number">8006399337547539</span> <span class="token punctuation">,</span> <span class="token number">16012798675095106</span> <span class="token punctuation">,</span> <span class="token number">16012798675095078</span> <span class="token punctuation">,</span> <span class="token number">8006399337547539</span> <span class="token punctuation">,</span> <span class="token number">72057594037927935</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>     
	<span class="token punctuation">&#123;</span><span class="token number">16012798675095106</span> <span class="token punctuation">,</span> <span class="token number">32025597350190213</span> <span class="token punctuation">,</span> <span class="token number">32025597350190184</span> <span class="token punctuation">,</span> <span class="token number">16012798675095106</span> <span class="token punctuation">,</span> <span class="token number">16012798675095078</span> <span class="token punctuation">,</span> <span class="token number">32025597350190184</span> <span class="token punctuation">,</span> <span class="token number">144115188075855871</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span> 
	<span class="token punctuation">&#123;</span><span class="token number">64051194700380397</span> <span class="token punctuation">,</span> <span class="token number">32025597350190213</span> <span class="token punctuation">,</span> <span class="token number">32025597350190184</span> <span class="token punctuation">,</span> <span class="token number">64051194700380397</span> <span class="token punctuation">,</span> <span class="token number">64051194700380368</span> <span class="token punctuation">,</span> <span class="token number">32025597350190184</span> <span class="token punctuation">,</span> <span class="token number">288230376151711743</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span> 
	<span class="token punctuation">&#123;</span><span class="token number">64051194700380397</span> <span class="token punctuation">,</span> <span class="token number">128102389400760795</span> <span class="token punctuation">,</span> <span class="token number">128102389400760765</span> <span class="token punctuation">,</span> <span class="token number">64051194700380397</span> <span class="token punctuation">,</span> <span class="token number">64051194700380368</span> <span class="token punctuation">,</span> <span class="token number">128102389400760765</span> <span class="token punctuation">,</span> <span class="token number">576460752303423487</span> <span class="token punctuation">&#125;</span> <span class="token punctuation">,</span>
	<span class="token punctuation">&#123;</span><span class="token number">256204778801521560</span> <span class="token punctuation">,</span> <span class="token number">128102389400760795</span> <span class="token punctuation">,</span> <span class="token number">128102389400760765</span> <span class="token punctuation">,</span> <span class="token number">256204778801521560</span> <span class="token punctuation">,</span> <span class="token number">256204778801521530</span> <span class="token punctuation">,</span> <span class="token number">128102389400760765</span> <span class="token punctuation">,</span> <span class="token number">1152921504606846975</span> <span class="token punctuation">&#125;</span> 
<span class="token punctuation">&#125;</span><span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> n<span class="token punctuation">;</span>
    cin<span class="token operator">>></span>n<span class="token punctuation">;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token string">"A->B:"</span><span class="token operator">&lt;&lt;</span>ans<span class="token punctuation">[</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token string">"A->C:"</span><span class="token operator">&lt;&lt;</span>ans<span class="token punctuation">[</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token string">"B->A:"</span><span class="token operator">&lt;&lt;</span>ans<span class="token punctuation">[</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token string">"B->C:"</span><span class="token operator">&lt;&lt;</span>ans<span class="token punctuation">[</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">]</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token string">"C->A:"</span><span class="token operator">&lt;&lt;</span>ans<span class="token punctuation">[</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">4</span><span class="token punctuation">]</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token string">"C->B:"</span><span class="token operator">&lt;&lt;</span>ans<span class="token punctuation">[</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">]</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token string">"SUM:"</span><span class="token operator">&lt;&lt;</span>ans<span class="token punctuation">[</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">6</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
这道题矩阵快速幂也可求解</p>
<h2 id="j-牛牛的宝可梦go">J： 牛牛的宝可梦Go</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200407080516808.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">3</span> <span class="token number">2</span>
<span class="token number">1</span> <span class="token number">2</span>
<span class="token number">2</span> <span class="token number">3</span>
<span class="token number">3</span>
<span class="token number">1</span> <span class="token number">1</span> <span class="token number">5</span>
<span class="token number">2</span> <span class="token number">3</span> <span class="token number">10</span>
<span class="token number">3</span> <span class="token number">2</span> <span class="token number">1</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">11</span></code></pre>
<p><strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">1</span> <span class="token number">0</span>
<span class="token number">3</span>
<span class="token number">1</span> <span class="token number">1</span> <span class="token number">100</span>
<span class="token number">100</span> <span class="token number">1</span> <span class="token number">10000</span>
<span class="token number">10000</span> <span class="token number">1</span> <span class="token number">1</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">10101</span></code></pre>
<p><strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">3</span> <span class="token number">2</span>
<span class="token number">1</span> <span class="token number">2</span>
<span class="token number">2</span> <span class="token number">3</span>
<span class="token number">1</span>
<span class="token number">1</span> <span class="token number">3</span> <span class="token number">1000000000</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">0</span></code></pre>
<p><strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">3</span> <span class="token number">2</span>
<span class="token number">1</span> <span class="token number">2</span>
<span class="token number">2</span> <span class="token number">3</span>
<span class="token number">1</span>
<span class="token number">1</span> <span class="token number">2</span> <span class="token number">1000000000</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">1000000000</span></code></pre>
<hr />
<p>这个题首先先求一遍最短路，这个求最短路的过程可以用flord实现。<br />
接下来类似最长上升子序列，但是显然这个好像不太好优化，考虑暴力<span
class="math inline">\(k^2\)</span>转移，由于地图的大小只有200，所以200步以后可以转移到任意位置，用这个性质可以优化<span
class="math inline">\(k^2\)</span>-&gt;200k。<br />
也就是说每次转移只暴力往前for200个，多余200个以上的时候记录一个前缀max，直接从这个前缀中转移。<br />
时间复杂度：<span
class="math inline">\(O\left(200k\right)\)</span><br />
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cctype></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;algorithm></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">il</span> <span class="token expression"><span class="token keyword">inline</span></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">ll</span> <span class="token expression"><span class="token keyword">long</span> <span class="token keyword">long</span></span></span>
il <span class="token keyword">char</span> <span class="token function">gc</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">static</span> <span class="token keyword">char</span> buf<span class="token punctuation">[</span><span class="token number">1</span><span class="token operator">&lt;&lt;</span><span class="token number">24</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token operator">*</span>p1<span class="token operator">=</span>buf<span class="token punctuation">,</span><span class="token operator">*</span>p2<span class="token operator">=</span>buf<span class="token punctuation">;</span>
    <span class="token keyword">return</span> p1<span class="token operator">==</span>p2<span class="token operator">&amp;&amp;</span><span class="token punctuation">(</span>p2<span class="token operator">=</span><span class="token punctuation">(</span>p1<span class="token operator">=</span>buf<span class="token punctuation">)</span><span class="token operator">+</span><span class="token function">fread</span><span class="token punctuation">(</span>buf<span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token operator">&lt;&lt;</span><span class="token number">24</span><span class="token punctuation">,</span><span class="token constant">stdin</span><span class="token punctuation">)</span><span class="token punctuation">,</span>p1<span class="token operator">==</span>p2<span class="token punctuation">)</span><span class="token operator">?</span> <span class="token constant">EOF</span><span class="token operator">:</span><span class="token operator">*</span>p1<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">gc</span> <span class="token expression">getchar</span></span>
il <span class="token keyword">int</span> <span class="token function">inn</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> x<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>c<span class="token operator">=</span><span class="token function">gc</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">bool</span> f<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token punctuation">;</span> <span class="token operator">!</span><span class="token function">isdigit</span><span class="token punctuation">(</span>c<span class="token punctuation">)</span><span class="token punctuation">;</span> c<span class="token operator">=</span><span class="token function">gc</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">if</span><span class="token punctuation">(</span>c<span class="token operator">==</span><span class="token char">'-'</span><span class="token punctuation">)</span> f<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>f<span class="token punctuation">)</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token punctuation">;</span> <span class="token function">isdigit</span><span class="token punctuation">(</span>c<span class="token punctuation">)</span><span class="token punctuation">;</span> c<span class="token operator">=</span><span class="token function">gc</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> x<span class="token operator">=</span><span class="token punctuation">(</span>x<span class="token operator">&lt;&lt;</span><span class="token number">3</span><span class="token punctuation">)</span><span class="token operator">+</span><span class="token punctuation">(</span>x<span class="token operator">&lt;&lt;</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token punctuation">(</span>c<span class="token operator">^</span><span class="token number">48</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">else</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token punctuation">;</span> <span class="token function">isdigit</span><span class="token punctuation">(</span>c<span class="token punctuation">)</span><span class="token punctuation">;</span> c<span class="token operator">=</span><span class="token function">gc</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> x<span class="token operator">=</span><span class="token punctuation">(</span>x<span class="token operator">&lt;&lt;</span><span class="token number">3</span><span class="token punctuation">)</span><span class="token operator">+</span><span class="token punctuation">(</span>x<span class="token operator">&lt;&lt;</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">+</span><span class="token punctuation">(</span>c<span class="token operator">^</span><span class="token number">48</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> x<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> N<span class="token operator">=</span><span class="token number">205</span><span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> K<span class="token operator">=</span><span class="token number">100005</span><span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> inf<span class="token operator">=</span><span class="token number">0x3f3f3f3f</span><span class="token punctuation">;</span>

<span class="token keyword">int</span> n<span class="token punctuation">,</span>m<span class="token punctuation">,</span>k<span class="token punctuation">,</span>l<span class="token punctuation">,</span>mp<span class="token punctuation">[</span>N<span class="token punctuation">]</span><span class="token punctuation">[</span>N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">struct</span> <span class="token class-name">node</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> t<span class="token punctuation">,</span>p<span class="token punctuation">,</span>v<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>a<span class="token punctuation">[</span>K<span class="token punctuation">]</span><span class="token punctuation">;</span>
ll f<span class="token punctuation">[</span>K<span class="token punctuation">]</span><span class="token punctuation">,</span>ans<span class="token punctuation">,</span>mx<span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">floyd</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> k<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span> k<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span> <span class="token operator">++</span>k<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span> j<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span> <span class="token operator">++</span>j<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                mp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">min</span><span class="token punctuation">(</span>mp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span>mp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">+</span>mp<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">bool</span> <span class="token function">cmp</span><span class="token punctuation">(</span><span class="token keyword">const</span> node <span class="token operator">&amp;</span>a<span class="token punctuation">,</span><span class="token keyword">const</span> node <span class="token operator">&amp;</span>b<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">return</span> a<span class="token punctuation">.</span>t<span class="token operator">&lt;</span>b<span class="token punctuation">.</span>t<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    n<span class="token operator">=</span><span class="token function">inn</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span>m<span class="token operator">=</span><span class="token function">inn</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">memset</span><span class="token punctuation">(</span>mp<span class="token punctuation">,</span><span class="token number">0x3f</span><span class="token punctuation">,</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>mp<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">&lt;=</span>m<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> u<span class="token operator">=</span><span class="token function">inn</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span>v<span class="token operator">=</span><span class="token function">inn</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        mp<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token punctuation">[</span>v<span class="token punctuation">]</span><span class="token operator">=</span>mp<span class="token punctuation">[</span>v<span class="token punctuation">]</span><span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> mp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token function">floyd</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    k<span class="token operator">=</span><span class="token function">inn</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">&lt;=</span>k<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>t<span class="token operator">=</span><span class="token function">inn</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>p<span class="token operator">=</span><span class="token function">inn</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>v<span class="token operator">=</span><span class="token function">inn</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>mp<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>p<span class="token punctuation">]</span><span class="token operator">==</span>inf<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token operator">--</span>i<span class="token punctuation">,</span><span class="token operator">--</span>k<span class="token punctuation">,</span><span class="token operator">--</span>n<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token function">sort</span><span class="token punctuation">(</span>a<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>a<span class="token operator">+</span>k<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>cmp<span class="token punctuation">)</span><span class="token punctuation">;</span>
    a<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>p<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">&lt;=</span>k<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>mp<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>p<span class="token punctuation">]</span><span class="token operator">></span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>t<span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>t<span class="token operator">-</span>a<span class="token punctuation">[</span>l<span class="token punctuation">]</span><span class="token punctuation">.</span>t<span class="token operator">>=</span>n<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            mx<span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span>mx<span class="token punctuation">,</span>f<span class="token punctuation">[</span>l<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>mx<span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span>l<span class="token punctuation">;</span> j<span class="token operator">&lt;</span>i<span class="token punctuation">;</span> <span class="token operator">++</span>j<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>mp<span class="token punctuation">[</span>a<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">.</span>p<span class="token punctuation">]</span><span class="token punctuation">[</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>p<span class="token punctuation">]</span><span class="token operator">&lt;=</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>t<span class="token operator">-</span>a<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">.</span>t<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span>f<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
        f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">+=</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>v<span class="token punctuation">;</span>
        ans<span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%lld\n"</span><span class="token punctuation">,</span>ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre></p>

    </div>

    
    
    
      


    <footer class="post-footer">
          <div class="reward-container">
  <div></div>
  <button>
    赞赏
  </button>
  <div class="post-reward">
      <div>
        <img src="/images/wechatpay.png" alt="Liu Kairui 微信">
        <span>微信</span>
      </div>
      <div>
        <img src="/images/alipay.png" alt="Liu Kairui 支付宝">
        <span>支付宝</span>
      </div>

  </div>
</div>

          

<div class="post-copyright">
<ul>
  <li class="post-copyright-author">
      <strong>本文作者： </strong>Liu Kairui
  </li>
  <li class="post-copyright-link">
      <strong>本文链接：</strong>
      <a href="http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A53%E9%A2%98%E8%A7%A3/" title="2020牛客寒假算法基础集训营3题解">http://liukairui.me/article/2020牛客寒假算法基础集训营3题解/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" rel="noopener" target="_blank"><i class="fab fa-fw fa-creative-commons"></i>BY-NC-SA</a> 许可协议。转载请注明出处！
  </li>
</ul>
</div>

          <div class="post-tags">
              <a href="/tags/%E7%AE%97%E6%B3%95/" rel="tag"><i class="fa fa-tag"></i> 算法</a>
              <a href="/tags/%E7%89%9B%E5%AE%A2/" rel="tag"><i class="fa fa-tag"></i> 牛客</a>
              <a href="/tags/ACM/" rel="tag"><i class="fa fa-tag"></i> ACM</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A52%E9%A2%98%E8%A7%A3/" rel="prev" title="2020牛客寒假算法基础集训营2题解">
                  <i class="fa fa-chevron-left"></i> 2020牛客寒假算法基础集训营2题解
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/article/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92-%E6%95%B0%E4%BD%8DDP/" rel="next" title="动态规划-数位DP">
                  动态规划-数位DP <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>






    <div class="comments" id="valine-comments"></div>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 2019 – 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Liu Kairui</span>
</div>
<div class="busuanzi-count">
    <span class="post-meta-item" id="busuanzi_container_site_uv">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-item" id="busuanzi_container_site_pv">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/muse/" rel="noopener" target="_blank">NexT.Muse</a> 强力驱动
  </div>
  <div class="addthis_inline_share_toolbox">
    <script src="//s7.addthis.com/js/300/addthis_widget.js#pubid=ra-6231eb6f709fc868" async="async"></script>
  </div><script
  async
  src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"
></script>

 
<script src="https://cdn.jsdelivr.net/npm/moment@2.22.2/moment.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/moment-precise-range-plugin@1.3.0/moment-precise-range.min.js"></script>
<script>
  function timer() {
    var ages = moment.preciseDiff(moment(),moment(20201101,"YYYYMMDD"));
    ages = ages.replace(/years?/, "年");
    ages = ages.replace(/months?/, "月");
    ages = ages.replace(/days?/, "天");
    ages = ages.replace(/hours?/, "小时");
    ages = ages.replace(/minutes?/, "分");
    ages = ages.replace(/seconds?/, "秒");
    ages = ages.replace(/\d+/g, '<span class="daysCnt" style="color:#1890ff">$&</span>');
    div.innerHTML = `我已在此等候你 ${ages}`;
    div.className="workDays";
  }
  var div = document.createElement("div");
  //插入到copyright之后
  var copyright = document.querySelector(".copyright");
  document.querySelector(".footer-inner").insertBefore(div, copyright.nextSibling);
  timer();
  setInterval("timer()",1000)
</script>



    </div>
  </footer>

  
  <script src="https://cdnjs.cloudflare.com/ajax/libs/animejs/3.2.1/anime.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/@next-theme/pjax@0.5.0/pjax.min.js" integrity="sha256-3NkoLDrmHLTYj7csHIZSr0MHAFTXth7Ua/DDt4MRUAg=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.6.0/jquery.min.js"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.5.7/jquery.fancybox.min.js" integrity="sha256-yt2kYMy0w8AbtF89WXb2P1rfjcP/HTHLT7097U8Y5b8=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/lozad.js/1.16.0/lozad.min.js"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/pangu/4.0.7/pangu.min.js"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/schemes/muse.js"></script><script src="/js/next-boot.js"></script><script src="/js/pjax.js"></script>

  
<script src="https://cdn.jsdelivr.net/npm/hexo-generator-searchdb@1.4.0/dist/search.js" integrity="sha256-vXZMYLEqsROAXkEw93GGIvaB2ab+QW6w3+1ahD9nXXA=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>


  <script class="next-config" data-name="mermaid" type="application/json">{"enable":true,"theme":"forest","js":{"url":"https://cdnjs.cloudflare.com/ajax/libs/mermaid/8.14.0/mermaid.min.js","integrity":"sha256-7wT34TI0pEBeEFoi4z+vhuSddGh6vUTMWdqJ2SDe2jg="}}</script>
  <script src="/js/third-party/tags/mermaid.js"></script>

  <script src="/js/third-party/fancybox.js"></script>

  <script src="/js/third-party/pace.js"></script>

  
  <script data-pjax async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>


  <script class="next-config" data-name="leancloud_visitors" type="application/json">{"enable":true,"app_id":"ABKlVtS4cyaWYEwunPyK3sXt-9Nh9j0Va","app_key":"xxGXdTTEGEVifs2TLB35844I","server_url":"https://abklvts4.lc-cn-e1-shared.com","security":false}</script>
  <script src="/js/third-party/statistics/lean-analytics.js"></script>


  

  <script class="next-config" data-name="enableMath" type="application/json">true</script><script class="next-config" data-name="mathjax" type="application/json">{"enable":true,"tags":"none","mhchem":true,"js":{"url":"https://cdnjs.cloudflare.com/ajax/libs/mathjax/3.2.0/es5/tex-mml-chtml.min.js"}}</script>
<script src="/js/third-party/math/mathjax.js"></script>


  <script src="https://cdnjs.cloudflare.com/ajax/libs/quicklink/2.2.0/quicklink.umd.js" integrity="sha256-4kQf9z5ntdQrzsBC3YSHnEz02Z9C1UeW/E9OgnvlzSY=" crossorigin="anonymous"></script>
  <script class="next-config" data-name="quicklink" type="application/json">{"enable":true,"home":false,"archive":false,"delay":true,"timeout":3000,"priority":true,"url":"http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A53%E9%A2%98%E8%A7%A3/"}</script>
  <script src="/js/third-party/quicklink.js"></script>
<script src="https://cdn.jsdelivr.net/npm/darkmode-js@1.5.7/lib/darkmode-js.min.js"></script>

<script>
var options = {
  bottom: '64px',
  right: 'unset',
  left: '32px',
  time: '0.5s',
  mixColor: 'transparent',
  backgroundColor: 'transparent',
  buttonColorDark: '#100f2c',
  buttonColorLight: '#fff',
  saveInCookies: true,
  label: '🌓',
  autoMatchOsTheme: true
}
const darkmode = new Darkmode(options);
window.darkmode = darkmode;
darkmode.showWidget();
</script>


<script class="next-config" data-name="valine" type="application/json">{"enable":true,"appId":"ABKlVtS4cyaWYEwunPyK3sXt-9Nh9j0Va","appKey":"xxGXdTTEGEVifs2TLB35844I","serverURLs":"https://abklvts4.lc-cn-e1-shared.com","placeholder":"请开始你的表演","avatar":"identicon","meta":["nick","mail","link"],"pageSize":10,"lang":"zh-CN","visitor":false,"comment_count":true,"recordIP":true,"enableQQ":true,"requiredFields":[],"el":"#valine-comments","path":"/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A53%E9%A2%98%E8%A7%A3/"}</script>
<script>
document.addEventListener('page:loaded', () => {
  NexT.utils.loadComments(CONFIG.valine.el)
    .then(() => NexT.utils.getScript(
      'https://cdn.jsdelivr.net/npm/valine@1.4.14/dist/Valine.min.js',
      { condition: window.Valine }
    ))
    .then(() => {
      new Valine(CONFIG.valine);
    });
});
</script>


  <script async src="/js/fireworks.js"></script>




  <script src="/js/activate-power-mode.min.js"></script>
  <script>
    POWERMODE.colorful = true;
    POWERMODE.shake = false;
    document.body.addEventListener('input', POWERMODE);
  </script>




  <script src="/js/wobblewindow.js"></script>
  <script>
    //只在桌面版网页启用特效 记得同步到header.njk
    if( window.innerWidth > 768  ){
      $(document).ready(function () {
        
          $('body>main>header').wobbleWindow({
            radius: 50,
            movementTop: false,
            movementLeft: false,
            movementRight: false,
            debug: false,
          });
        

        //
        //  $('body header>aside').wobbleWindow({
        //    radius: 50,
        //    movementLeft: false,
        //    movementTop: false,
        //    movementBottom: false,
        //    position: 'fixed',
        //    debug: false,
        //  });
        //

        
          $('body>footer').wobbleWindow({
            radius: 50,
            movementBottom: false,
            movementLeft: false,
            movementRight: false,
            debug: false,
          });
        
      });
    }
  </script>


 
<script>
  $(document).ready(function(){
    var beian = document.querySelector(".footer-inner > .beian > a");
    var cpr=document.querySelector(".footer-inner > .copyright");
    var cnz=document.querySelector(".workDays");//.parentNode;
    var bsz=document.querySelector(".busuanzi-count");
    if(cnz!=null&&bsz!=null)
      cnz.parentNode.insertBefore(bsz,cnz);
    if(bsz == null || bsz == undefined || document.querySelector("#busuanzi_value_site_pv").innerText=="" || document.querySelector("#busuanzi_value_site_uv").innerText == "")
      bsz.remove();
    checkIndex();
    if(beian){cpr.classList.add('split-line');cpr.appendChild(beian);}
  })
  $(document).on('pjax:complete',checkIndex);
</script>



<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"log":false,"model":{"jsonPath":"/live2dw/assets/hijiki.model.json"},"display":{"position":"right","width":150,"height":300},"mobile":{"show":false},"react":{"opacity":0.7}});</script></body>
</html>
